在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
// 参数： // numbers: 一个整数组 // length： 数组的长度 // duplication：输出数组中的一个重复的数字 //返回值： // true - 输入有效，并且数组中存在重复的数字 // false - 输入无效，或者数组中没有重复的数字 bool duplicate(int numbers[], int length, int *duplication) { if(numbers == nullptr || length <= 0) return false; for (int i = 0; i < length; ++i) { if (numbers[i] < 0 || numbers[i] > length - 1) return false; } for (int i = 0; i < length; ++i) { while (numbers[i] != i) { if (numbers[i] == numbers[numbers[i]]) { *duplication = numbers[i]; return true; } // 交换numbers[i]和numbers[numbers[i]] int temp = numbers[i]; numbers[i] = numbers[numbers[i]]; numbers[numbers[i]] = temp; } } return false; }
时间复杂度为O（n），空间复杂度为O（1）
题目：在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。
int countRange(const int *numbers, int length, int start, int end); int getDuplication(const int* numbers, int length) { if (numbers == nullptr || length <= 0) return -1; int start = 1; int end = length - 1; while (end >= start) { int middle = ((end - start) >> 1) + start; int count = countRange(numbers, length, start, middle); if (end == start) { if (count > 1) return start; else break; } // 如果[start, middle]内的数量超过middle - start + 1，证明里面一定有重复的数字 if (count > (middle - start + 1)) end = middle; else start = middle + 1; } return -1; } int countRange(const int *numbers, int length, int start, int end) { if (numbers == nullptr) return 0; int count = 0; // 统计一个区间内的数字数量 for (int i = 0; i < length; i++) { if (numbers[i] >= start && numbers[i] <= end) ++count; } return count; }
上述代码按照二分查找的思路，如果输入长度为n的数组，那么函数countRange将被调用O（logn）次，每次需要O（n）的时间，因此总的时间复杂度是O（nlogn），空间复杂度为O（1），但是这种算法不能保证找出所有重复的数字。
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution { public: bool Find(int target, vector<vector<int> > array) { if(array.size() != 0) { int row = 0; // 二维数组列的求法 int col = array[0].size() - 1; while(row < array.size() && col >= 0) { if(array[row][col] == target) return true; else if(array[row][col] > target) --col; else ++row; } } return false; } };
原文：https://www.cnblogs.com/gezhuangzhuang/p/10686620.html