常州网站建设平台,新开网店怎么推广,ui设计师是啥,wordpress页面与文章题目描述 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的#xff0c;但不知道有几个数字是重复的#xff0c;也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 Input:
{2, 3, 1, 0, 2, 5}Output:
2 思路 给出了长度为n且数组… 题目描述 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的但不知道有几个数字是重复的也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 Input:
{2, 3, 1, 0, 2, 5}Output:
2 思路 给出了长度为n且数组内的数字的范围是0-n0-n的范围恰好是这个数组的索引的范围。思路是遍历整个数组把值为j的元素放到索引为j的位置上如果整个数组没有重复那么在放置的过程中就不会发生冲突。 {3,0,2,1}
{0,1,2,3} 如果至少有一个元素发生了至少一次冲突那么置换完毕后的数组的长度肯定小于原有数组的长度。 {3,0,2,2}
{0,2,3} 实现 这种需要置换的肯定把置换的方法写出来 public static void swap(int[]arr,int i,int j){/*** 把数组arr里位置i j的元素交换位置*/int temp arr[i];arr[i] arr[j];arr[j] temp;} 我的第一版是这样的看起来好像没啥问题。遍历整个数组然后把arr[i]位置的元素和arr[arr[i]]位置的元素交换。 public static boolean isDuplicate(int[] arr){int length arr.length;for(int i0; ilength-1; i){if(arr[i] arr[arr[i]])return true;else {swap(arr, i, arr[i]);}}return false;} 我拿[3,1,0,2]这个数组测试的时候返回的是true这显然是不对的。调试之后发现在i1即循环一次后数组变成了{3,1,2,0}返回true。返回的条件是arr[1] arr[arr[1]]。到这里我就看到我这个算法的问题了我的算法只有在原始数组是完全乱序的前提下才会返回正确的结果也即我的算法是判断一个数组是否完全乱序。因为{3,1,2,0}中的1处在了正确的位置所以会导致提前退出。 错误的原因是我没有考虑到一个数组的arr[i]i的情况下也会出现上述的交换冲突。 public static boolean isDuplicate2(int[] arr){int length arr.length;for(int i0; ilength-1; i){if(arr[i] arr[arr[i]] arr[i] ! i)return true;else {swap(arr, i, arr[i]);}}return false;} 转载于:https://www.cnblogs.com/AshOfTime/p/10391657.html
