长为N的数组，元素范围是0-N-1，其中只有一个数是重复的，找出这个重复元素...

思路：如果限制空间复杂度为O（1），我们就无法采用哈希表的方法去求解。题目中数组中所以数字都在范围[0， N-1]，因此哈希表的大小为N即可。因此我们实际要做的就是对N个范围为0到N-1的数进行哈希，而哈希表的大小刚好为N。对排序算法比较熟悉的同学不难发现这与一种经典的排序算法——基数排序非常类似。而基数排序的时间空间复杂度刚好符合题目要求！因此尝试使用基数排序来解这道面试题。

代码如下：

#include<iostream> #include<vector> using namespace std;int searchDulnum(vector<int>a){for (int i = 0; i < a.size(); i++){while (a[i] != i){if (a[i] == a[a[i]])return a[i];else{swap(a[i], a[a[i]]);}}}return -1;}int main(){vector<int>a = { 0, 1, 2, 3, 4, 5, 6, 6, 8, 9 };int res = searchDulnum(a);cout << res << endl;system("pause");return 0; }

 

---

还有一类似方法题:求第一个确实正数，限定空间复杂度为O（1）

思路是把1放在数组第一个位置nums[0]，2放在第二个位置nums[1]，即需要把nums[i]放在nums[nums[i] - 1]上，将数组的第i位存正数i+1。那么我们遍历整个数组，如果nums[i] != i + 1, 而nums[i]为整数且不大于n，另外nums[i]不等于nums[nums[i] - 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数。

int firstMissingPositive(vector<int>& nums) {int n=nums.size();int i=0;for(int i=0;i<n;i++){while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){swap(nums[nums[i]-1],nums[i]);}}for(int i=0;i<n;i++){if(nums[i]!=i+1)return i+1;}return n+1;}

 

转载于:https://www.cnblogs.com/inception6-lxc/p/9316285.html

总结

以上是生活随笔为你收集整理的长为N的数组，元素范围是0-N-1，其中只有一个数是重复的，找出这个重复元素...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。