在数组中重复的元素 [英] Duplicate element in array
问题描述
这是一种涉及到<一个href="http://stackoverflow.com/questions/2605766/how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers">this的问题，但有点扭捏。 我们给予含1和1000之间的整数数组。 从1到1000的每整数数组中一次，但一个是在阵列中的两倍。 （即我从列表中删除一个独特的元素，并介绍这已经在列表中重复的元素，记住数组的大小仍然是1000）
This is kind of related to this question, but a little tweaked . We are given an array containing integers between 1 and 1000. Every integer from 1 and 1000 is in the array once, but one is in the array twice. (i.e. I remove a unique element from the list and introduce a duplicate element which is already in the list,remember the size of the array is still 1000)
- 在确定哪些整数数组中两次
- 您能做到这一点，同时通过遍历数组只有一次？
在这我已经发布这是一个不同的问题完全链接。
In the link that i have posted it's a different question altogether.
我的解决方法：
-
排序数组，然后发现，如果两个元素在一起。 （平均情况O（n日志（N）））
sorting the array and then finding if the two elements are together. (avg case O(nlog(n)))
创建一个位阵列，1000位（也花不了多少内存）。与0存储在每个位字段。循环访问的1000个元素的数组，并翻转位符号与数组的值的位阵列的索引。
Create a bit-array with a 1000 bits (won't take much memory). with 0 stored in each of the bit field. Iterate through the array of 1000 elements and flip the bit sign in the bit-array's index with the value of the array .
即。 （如果该数组的第0个位置存储值548，我们翻转比特数组1中第548位位）。
i.e. (if the 0th position of the array stores the value 548, we flip the 548th bit in the bit-array to 1).
与已翻转的1场将是重复的元素
The field with already flipped as 1 will be the repeated element
溶液2迭代阵列只有一次。
Solution2 iterates the array only once.
现在，我正在读关于伸缩系列的，我不明白它完全。但有一个概念，在那里（或离散数学），我们可以只总结一些东西，别的东西减去，以获得重复的号码？
Now, I was reading about the 'Telescoping series', i haven't understood it fully. but is there a concept in there (or in discrete math) where we can just sum something and subtract with something else to get the duplicate number?
推荐答案
计算数组的总和让它成为取值并让重复的元素是 X 。重复的元素可以通过采取取值和数组的款项，但不得重复元素： X = S-（1000 * 1001）/ 2
Calculate the sum of the array let it be S and let the repeated element be x. The repeated element can be determined by taking the difference between S and the sum of the array without the repeated element: x=S- (1000*(1001))/2.
这篇关于在数组中重复的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
