我的常规方法:
由于数组长度 n, 所有数据的大小都在 0 到 n-1 之间, 所以考虑把每一位上的数字都放到应该呆的位置. 如果 nums[i]!=i 并且 nums[i]该呆的位置 (nums[nums[i]]) 已经等于 nums[i]了, 说明出现了重复数字.
- class Solution {
- public:
- // Parameters:
- // numbers: an array of integers
- // length: the length of array numbers
- // duplication: (Output) the duplicated number in the array number
- // Return value: true if the input is valid, and there are some duplications in the array number
- // otherwise false
- bool duplicate(int numbers[], int length, int* duplication) {
- for(int i=0;i<length;++i){
- if(numbers[i]==i){// 第 i 位放 i
- continue;
- }
- while(numbers[i]!=i and numbers[numbers[i]]!=numbers[i]){
- int temp=numbers[numbers[i]];
- numbers[numbers[i]]=numbers[i];
- numbers[i]=temp;
- }
- if(numbers[i]!=i){*duplication=numbers[i]; return true;}
- }
- return false;
- }
- };
评论区一个方法:
- bool duplicate(int numbers[], int length, int* duplication) {
- for(int i=0;i!=length;++i){
- int index=numbers[i]%length;
- if(numbers[index]>=length){
- *duplication=index;
- return 1;
- }
- numbers[index]+=length;
- }
- return 0;
- }
遍历到第 i 位, 当前数字为 nums[i], 那么就在 nums[i]索引处做一个标记, 即将 nums[nums[i]]加上数组的长度, 以此作为标记, 记录 nums[i]这个数已经出现过了.
之后如果遍历到 j(j>i), 当前数字为 nums[j], 去检查 nums[j]索引处是不是已经做过标记了 (即 nums[nums[j]] 的值是否大于数组长度), 如果做过标记了说明当前 nums[j]就是一个重复出现的数字.
其实写到这, 原理和我的方法是类似的, 都是将遍历过的数字在对应索引位置做好记录, 以备后期再查阅. 时间复杂度同样都是 O(N), 只是这个方法不打印出来每次数组的结果, 有些不好理解就是了..
下面是运行截图, 每次循环都打印一次数组的结果:
来源: http://www.bubuko.com/infodetail-3415721.html