找出重复数
题目:1 ~ 1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来,不用辅助存储空间,能否设计一个算法实现?
姑且令该数组为int[] a
解法1:数组累和 - (1+2+3+...+.. + 999 + 1000)= 所求结果
public int find(int[] a) {
int t = 1000 * (1000 + 1) / 2; // 1 ~ 1000的累和
int sum = 0;
for(int i = 0;i < a.length;i++) {
sum += a[i];
}
return (sum - t);
}
解法2:异或
将所有的数全部异或,得到的结果与1^2^3^...^1000的结果进行异或,得到的结果就是重复数。
但是这个算法虽然很简单,但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。
首先是异或运算满足交换律、结合律。
所以,1^2^...^n^...^n^...^1000,无论这两个n出现在什么位置,都可以转换成为1^2^...^1000^(n^n)的形式。
其次,对于任何数x,都有x^x=0,x^0=x。
所以1^2^...^n^...^n^...^1000 = 1^2^...^1000^(n^n)= 1^2^...^1000^0 = 1^2^...^1000(即序列中除了n的所有数的异或)。
令,1^2^...^1000(序列中不包含n)的结果为T
则1^2^...^1000(序列中包含n)的结果就是T^n。
T^(T^n)=n。
所以,将所有的数全部异或,得到的结果与1^2^3^...^1000的结果进行异或,得到的结果就是重复数。
public int find(int[] a) {
int t1 = 0;
int t2 = 0;
for(int i = 0;i < a.length;i++) {
t1 ^= a[i];
}
for(int i = 1;i <= 1000;i++) {
t2 ^= i;
}
return (t1 ^ t2);
}
遗留问题:如果放入数组a中的数为:1000个不连续且互不相同的数(设其组成的数组为n) + 重复数(取自数组n),又如何求取这个重复数呢,要保证算法的效率哦
分享到:
相关推荐
本文实例讲述了C语言查找数组里数字重复次数的方法。分享给大家供大家参考。具体如下: #include stdafx.h #include #include using namespace std; int main() { int myarray[10]={4,3,7,4,8,7,9,4,3,6}; ...
借助HashMap找到重复出现的数字 & 没有出现的数字。
能够查询各种文件类型的重复文件,并且删除其中重复文件 比较不错的软件
就拿去除重复行来说吧,几十万的数据用它就对了,比excel和sql快多了。导入进去,选择排序,去除重复行。
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几...请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
剑指offer面试题库中第三题的C语言代码。在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。 程序源代码: main() { ...
不修改数组找出重复的数字.md
在一个长度为N+1的数组里面的所有数字都在范围1~N范围内,所以数组至少有一个数字是重复的,请找出重复数字,但是不能修改输入的数组。 2 思路 思路1: 我们开辟一个新的数组,初始化为0,然后把原始数组每个数据的...
找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
找出数组中重复的数字。 一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。 数组中某些数字是重复的,但不知道有几个数字重复了, 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例...
C++语言实现查找数组中第二大和第二小的数值,并且判断数组中重复次数最高的数
找出数组中重复的数字.md
一个给定的正整数数组,数组中有的数字有重复,找出数组中没有重复的数
用筛选法删除输入的10个数中的重复的数字。
主要为大家详细介绍了Java如何找出数组中重复的数字,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
网上那种找出两个数组重复元素的代码复杂度较高,这个比较简单,一次循环搞定
找出两数组相同的数(VB6.0源代码编写)比较并找出两数组相同的数,显示出相同的数值显示两个数组中相同数的位置等.
自用工具 易语言 源码 资源 文本处理
1.表中有id和name 两个字段,查询出name重复的所有数据 select * from xi a where (a.username) in (select username from xi group by username having count(*) > 1) 2、查询出所有数据进行分组之后,和重复数据...