(剑指Offer)面试题51:数组中重复的数字
2023-09-14 09:00:36 时间
题目:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。
思路:
1、排序
将数组排序,然后扫描排序后的数组即可。
时间复杂度:O(nlogn),空间复杂度:O(1)
2、哈希表
从头到尾扫描数组,每扫描到一个数字,判断该数字是否在哈希表中,如果该哈希表还没有这个数字,那么加入哈希表,如果已经存在,则返回该数字;
时间复杂度:O(n),空间复杂度:O(n)
3、交换
0~n-1正常的排序应该是A[i]=i;因此可以通过交换的方式,将它们都各自放回属于自己的位置;
从头到尾扫描数组A,当扫描到下标为i的数字m时,首先比较这个数字m是不是等于i,
如果是,则继续扫描下一个数字;
如果不是,则判断它和A[m]是否相等,如果是,则找到了第一个重复的数字(在下标为i和m的位置都出现了m);如果不是,则把A[i]和A[m]交换,即把m放回属于它的位置;
重复上述过程,直至找到一个重复的数字;
时间复杂度:O(n),空间复杂度:O(1)
(将每个数字放到属于自己的位置最多交换两次)
代码:
交换
#include <iostream> using namespace std; bool duplicate(int numbers[],int length,int* duplication){ if(numbers==NULL || length<=1){ duplication=NULL; return false; } for(int i=0;i<length;i++){ while(numbers[i]!=i){ if(numbers[i]==numbers[numbers[i]]){ *duplication=numbers[i]; return true; } int tmp=numbers[i]; numbers[i]=numbers[tmp]; numbers[tmp]=tmp; } } return false; } int main() { int A[]={2,3,1,0,2,5,3}; int len=sizeof(A)/sizeof(A[0]); int duplication; cout << duplicate(A,len,&duplication) << endl; cout << duplication << endl; return 0; }
在线测试OJ:
http://www.nowcoder.com/books/coding-interviews/623a5ac0ea5b4e5f95552655361ae0a8?rp=2
AC代码:
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) { if(numbers==NULL || length<=1){ duplication=NULL; return false; } for(int i=0;i<length;i++){ while(numbers[i]!=i){ if(numbers[i]==numbers[numbers[i]]){ *duplication=numbers[i]; return true; } int tmp=numbers[i]; numbers[i]=numbers[tmp]; numbers[tmp]=tmp; } } return false; } };
相关文章
- 并发编程篇:java 高并发面试题
- HTML和CSS面试题及答案总结一
- 百度前端必会手写面试题及答案
- 我的react面试题笔记整理(附答案)
- 暴力解析美团最新JVM面试题:无限执行
- Go 常见算法面试题篇(三):高效调整数组数值顺序
- c#面试题抽象类和接口的区别-SSH面试题.doc
- 前端常见手写面试题集锦_2023-02-23
- 腾讯算法面试题:求解非递减数组范围下标
- 前端常考vue面试题(必备)_2023-03-15
- BAT算法面试题(12)--环形链表(哈希表法)
- python面试题大全(一)详解编程语言
- 面试之道:完整MySQL面试题大全(mysql面试题大全)
- Redis常见面试题及解答精选(经常问redis的面试题)