题目
一个大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找到至少一个重复元素,要求O(1)空间和O(n)时间。
思路一
寻找重复元素,很容易想到建立哈希表来完成,遍历一遍数组就可以将每个元素映射到哈希表中。如果哈希表中已经存在这个元素则说明这就是个重复元素。这种方法可以很方便的在O(n)时间内完成对重复元素的查找。可是题目要求在O(1)的空间。因此采用哈希表这种解法肯定在空间复杂度上是不符合要求的。题目中数组中所以数字都在[0, n-1]区间范围内,因此哈希表的大小为n。因此我们实际要做的就是对n个范围为0到n-1的数进行哈希,而哈希表的大小刚好为n。对排序算法比较熟悉的同学不难发现这与一种经典的排序算法(基数排序)非常类似。而基数排序的时间空间复杂度刚好符合题目要求。因此尝试使用基数排序来解这道面试题。
代码
#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
int IsReplication(int a[],int n){
if(n <= 0){
return -1;
}
for(int i = 0;i < n;){
if(a[i] != i){
if(a[i] == a[a[i]]){
return a[i];
}
swap(a[i],a[a[i]]);
}
else{
++i;
}
}
return -1;
}
};
int main() {
Solution solution;
int num[] = {6,1,4,7,5,3,6,2};
int result = solution.IsReplication(num,8);
cout<<result<<endl;
}
思路二
第一次遍历:对于每一个A[i] = A[i] * n
第二次遍历:对于每一个i,A[A[i]/n]++
第三次遍历:对于每一个i,A[i] % n就是出现次数
A[i]应该出现在A中的A[i]位置,乘以n、再除以n,很容易的来回变换;第二次遍历,对于A[i]本来所在的位置不断增1,但绝对不对超出n的,那每一个i出现的次数,就是A[i]对n取余。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> Replication(int a[],int n){
vector<int> result;
if(n <= 0){
return result;
}
for(int i = 0;i < n;++i){
a[i] *= n;
}
for(int i = 0;i < n;++i){
++a[a[i]/n];
}
int count;
for(int i = 0;i < n;++i){
count = a[i] % n;
if(count > 1){
result.push_back(i);
}
}
return result;
}
};
int main() {
Solution solution;
int num[] = {6,1,3,7,5,3,6,2};
vector<int> result = solution.Replication(num,8);
for(int i = 0;i < result.size();++i){
cout<<result[i]<<endl;
}
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
数组 - 需要参加面试的人
1.数组求和?(用递归,只用一行代码) 2.求数组的最大值和最小值(用递归的方法,将数组分为左右两个子数组,返回条件是左右数组只剩一个或两个元素)
面试题53 - I. 在排序数组中查找数字 I题目链接面试题53 - I. 在排序数组中查找数字 I题目描述统计一个数字在排序数组中出现的次数。题解public
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2...
嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题
程序员面试题100题(63)-数组中三个只出现一次的数字[算法].pdf,这是一份不错的文件
面试题56 - I. 数组中数字出现的次数题目链接面试题56 - I. 数组中数字出现的次数题目描述一个整型数组里除了两个数字之外,其他的数字都出现了两次。传出
Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 ...
剑指offer面试题66--构建乘积数组给定一个数组A[0, 1,...n - 1],请构建一个数组A[0, 1,...n - 1],其中B中的元素B[i] =
c语言面试题 c语言面试题之双指针按奇偶排序数组
自己做老师时整理出来的一维数组题目,可用于教学、测试、面试题,需要的拿走
c语言面试题 c语言面试题之双指针数组中的K-diff数对
题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组...NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 解题思路参考博客
剑指offer面试题库中第三题的C语言代码。在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
PHP经典面试题 PHP经典面试题 PHP经典面试题 PHP经典面试题 PHP经典面试题
面试题总结:数组和链表的区别 数组和链表.pdf
C++面试题 1.是不是一个父类写了一个virtual 函数,如果子类覆盖它的函数不加virtual ,也能实现多态? virtual修饰符会被隐形继承的。 private 也被集成,只事派生类没有访问权限而已 virtual可加可不加 子类的...
C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题
面试题11. 旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5]
面试题66. 构建乘积数组题目链接面试题66. 构建乘积数组题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B