-
#include <iostream> #include <vector> /* 面试题3:数组中重复的数字: 问题: 在len长、值域为【1,len-1】的数组中找到重复的那个数字,不能修改原数组 解决: 哈希表,时间空间复杂度都是o(n) 二分查找,不断的查找重复的数字是在值域的前半区间内,还是在后半区间内 时间复杂度为o(nlgn), 空间复杂度为o(1) */ using namespace std; // 返回[low, up]范围内是否有重复数字 bool check_repeat(const vector<int> array_n, const int len, const int up,const int low) { int number = 0; for(int i = 0; i < len; i++) { if (array_n[i]>=low && array_n[i]<=up) number++; } if (up-low+1 < number) return true; else return false; } //在len长、值域为【1,len-1】的数组中找到重复的那个数字 int getduplication(const vector<int> array_n, const int len) { if (array_n.size() == 0) return -1; for (int i = 0; i < len; i++) if (array_n[i] > len-1 || array_n[i] < 1) return -2; int up = len-1; int low = 0; while(true) { if (up == low) break; if (check_repeat(array_n, len, up, low/2+up/2)) low = low/2+up/2; else up = low/2+up/2-1; } return up; } int main(void) { int len; cin >> len; vector<int> array_n(len, 0); for (int i = 0; i < len; i++) cin >> array_n[i]; int duplication = getduplication(array_n, len); if (duplication == -1) cout << "输入的数组为空"; else if (duplication == -2) cout << "输入的数组的值域不在【" << 1 << "," << len-1 << "】之间"; else cout << duplication; return 0; }
面试题3:数组中重复的数字,不能修改原数组
转载于:https://www.cnblogs.com/jkn1234/p/8878176.html