blocks|key|3051199|text|只需将它们相加，然后减去如果只使用1001个数字时所期望的总数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3051200|例如：|3051201|Input:+1,2,3,2,4+=>+12
Expected:+1,2,3,4+=>+10

Input+-+Expected+=>+2|code-block|syntax|javascript|3051202|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Just add them all up, and subtract the total you would expect if only 1001 numbers were used from that.

Eg:

<pre><code>Input: 1,2,3,2,4 =&gt; 12
Expected: 1,2,3,4 =&gt; 10

Input - Expected =&gt; 2
</code></pre>

blocks|key|309167|text|Franci+Penov的解决方案的非破坏性版本。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|309168|这可以通过使用XOR运算符来完成。|offset|length|style|CODE|309169|假设我们有一个大小为5的数组：4,+3,+1,+2,+2|309170|这些是在指数：*+0,+1,+2,+3,+4|309171|现在对所有元素和所有索引执行XOR。我们得到2，它是重复的元素。这是因为，0在XORing中不起任何作用。剩余的n-1索引与数组中相同的n-1元素配对，数组中唯一未配对的元素将是副本。|309172|int+i;
int+dupe+=+0;
for(i+=+0;+i+<+N;+i%2B%2B)+{
++++dupe+=+dupe+%5E+arr[i]+%5E+i;
}
//+dupe+has+the+duplicate.|code-block|syntax|javascript|309173|这种解决方案的最大特点是它不会出现基于加法的解决方案中出现的溢出问题。|309174|由于这是一个面试问题，最好从基于加法的解决方案开始，确定溢出限制，然后给出基于XOR的解决方案:)|309175|这使用了一个额外的变量，因此不能完全满足问题中的要求。|309176|entityMap^0|0|7|3|0|A|1|F|D|0|9|D|0|E|3|M|1|11|1|1K|3|1W|3|0|0|0|13|3|1B|2|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@$D|12|E|13|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|14|8|@$D|15|E|16|F|G]|$D|17|E|18|F|G]]|9|@]|A|$]]|$1|J|3|K|5|6|7|19|8|@$D|1A|E|1B|F|G]]|9|@]|A|$]]|$1|L|3|M|5|6|7|1C|8|@$D|1D|E|1E|F|G]|$D|1F|E|1G|F|G]|$D|1H|E|1I|F|G]|$D|1J|E|1K|F|G]|$D|1L|E|1M|F|G]]|9|@]|A|$]]|$1|N|3|O|5|P|7|1N|8|@]|9|@]|A|$Q|R]]|$1|S|3|T|5|6|7|1O|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1P|8|@$D|1Q|E|1R|F|G]|$D|1S|E|1T|F|G]]|9|@]|A|$]]|$1|W|3|X|5|6|7|1U|8|@]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1V|8|@]|9|@]|A|$]]]|Z|$]]

A non destructive version of solution by Franci Penov.

This can be done by making use of the <code>XOR</code> operator. 

Lets say we have an array of size <code>5</code>: <code>4, 3, 1, 2, 2</code> 
Which are at the index: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <code>0, 1, 2, 3, 4</code>

Now do an <code>XOR</code> of all the elements and all the indices. We get <code>2</code>, which is the duplicate element. This happens because, <code>0</code> plays no role in the XORing. The remaining <code>n-1</code> indices pair with same <code>n-1</code> elements in the array and the only unpaired element in the array will be the duplicate.

<pre class="lang-c prettyprint-override"><code>int i;
int dupe = 0;
for(i = 0; i &lt; N; i++) {
 dupe = dupe ^ arr[i] ^ i;
}
// dupe has the duplicate.
</code></pre>

The best feature of this solution is that it does not suffer from overflow problems that is seen in the addition based solution.

Since this is an interview question, it would be best to start with the addition based solution, identify the overflow limitation and then give the <code>XOR</code> based solution <code>:)</code>

This makes use of an additional variable so does not meet the requirements in the question completely.

blocks|key|3264962|text|把所有的数字加在一起。最终的总和将是1%2B2%2B...%2B1000%2Bduplicate数字。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3264963|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Add all the numbers together. The final sum will be the 1+2+...+1000+duplicate number.

blocks|key|3265155|text|套用弗朗西斯·佩诺夫的解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3265156|(通常的)问题是:给定一个任意长度的整数数组，其中只包含重复了偶数次的元素，除了一个重复了奇数次的值之外，找出这个值。|3265157|解决方案是：|3265158|acc+=+0
for+i+in+array:+acc+=+acc+%5E+i|code-block|syntax|javascript|3265159|你目前的问题是适应。诀窍是你要找到重复两次的元素，所以你需要调整解决方案来补偿这种怪癖。|3265160|acc+=+0
for+i+in+len(array):+acc+=+acc+%5E+i+%5E+array[i]|3265161|这就是Francis的解决方案最终要做的，尽管它会销毁整个数组(顺便说一句，它只能销毁第一个或最后一个元素……)|3265162|但是由于你需要额外的存储空间来存储索引，我认为如果你也使用额外的整数，那是可以理解的…这种限制很可能是因为他们想阻止您使用数组。|3265163|如果他们需要O(1)空间(1000可以被视为N，因为它在这里是任意的)，它会被更准确地表达出来。|offset|length|style|CODE|3265164|entityMap^0|0|0|0|0|0|0|0|0|6|4|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|13|8|@]|9|@]|A|$I|J]]|$1|K|3|L|5|6|7|14|8|@]|9|@]|A|$]]|$1|M|3|N|5|H|7|15|8|@]|9|@]|A|$I|J]]|$1|O|3|P|5|6|7|16|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|17|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|18|8|@$U|19|V|1A|W|X]]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|Z|$]]

To paraphrase Francis Penov's solution.

The (usual) problem is: given an array of integers of arbitrary length that contain only elements repeated an even times of times except for one value which is repeated an odd times of times, find out this value.

The solution is:

<pre><code>acc = 0
for i in array: acc = acc ^ i
</code></pre>

Your current problem is an adaptation. The trick is that you are to find the element that is repeated twice so you need to adapt solution to compensate for this quirk.

<pre><code>acc = 0
for i in len(array): acc = acc ^ i ^ array[i]
</code></pre>

Which is what Francis' solution does in the end, although it destroys the whole array (by the way, it could only destroy the first or last element...)

But since you need extra-storage for the index, I think you'll be forgiven if you also use an extra integer... The restriction is most probably because they want to prevent you from using an array.

It would have been phrased more accurately if they had required <code>O(1)</code> space (1000 can be seen as N since it's arbitrary here).

blocks|key|3051294|text|将所有数字相加。整数1..1000的和是(1000*1001)/2，与你得到的数字的差值是你的数字。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3051295|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Add all numbers. The sum of integers 1..1000 is (1000*1001)/2. The difference from what you get is your number.

blocks|key|3051517|text|Python中的单行解决方案|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3051518|arr+=+[1,3,2,4,2]
print+reduce(lambda+acc,+(i,+x):+acc+%5E+i+%5E+x,+enumerate(arr),+0)
#+->+2|code-block|syntax|javascript|3051519|关于它的工作原理的解释在@Matthieu+M.'s+answer中。|offset|length|3051520|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/2605766/how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers/2606065#2606065^0|0|0|C|L|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@$I|V|J|W|1|X]]|A|$]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

<h3>One line solution in Python</h3>
<pre class="lang-py prettyprint-override"><code>arr = [1,3,2,4,2]
print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0)
# -&gt; 2
</code></pre>
Explanation on why it works is in <a href="https://stackoverflow.com/questions/2605766/how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers/2606065#2606065">@Matthieu M.'s answer</a>.

blocks|key|311267|text|如果您知道我们有确切的数字1-1000，您可以将结果相加，然后从总数中减去500500+(sum(1,+1000))。这将给出重复的数字，因为sum(array)+=+sum(1,+1000)+%2B+repeated+number。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|311268|entityMap^0|11|6|19|C|1Z|17|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|O|8|@]|D|@]|E|$]]]|G|$]]

If you know that we have the exact numbers 1-1000, you can add up the results and subtract <code>500500</code> (<code>sum(1, 1000)</code>) from the total. This will give the repeated number because <code>sum(array) = sum(1, 1000) + repeated number</code>.

blocks|key|312133|text|没有额外的存储需求(除了循环变量)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|312134|int+length+=+(sizeof+array)+/+(sizeof+array[0]);
for(int+i+=+1;+i+<+length;+i%2B%2B)+{
+++array[0]+%2B=+array[i];
}

printf(
++++"Answer+:+%25d\n",
++++(+array[0]+-+(length+*+(length+%2B+1))+/+2+)
);|code-block|syntax|javascript|312135|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

No extra storage requirement (apart from loop variable).

<pre class="lang-c prettyprint-override"><code>int length = (sizeof array) / (sizeof array[0]);
for(int i = 1; i &lt; length; i++) {
 array[0] += array[i];
}

printf(
 "Answer : %d\n",
 ( array[0] - (length * (length + 1)) / 2 )
);
</code></pre>

blocks|key|314248|text|参数和callstack算不算辅助存储？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|314249|int+sumRemaining(int*+remaining,+int+count)+{
++++if+(!count)+{
++++++++return+0;
++++}
++++return+remaining[0]+%2B+sumRemaining(remaining+%2B+1,+count+-+1);
}|code-block|syntax|javascript|314250|printf("duplicate+is+%25d",+sumRemaining(array,+1001)+-+500500);|314251|314252|编辑:尾部调用版本|314253|int+sumRemaining(int*+remaining,+int+count,+int+sumSoFar)+{
++++if+(!count)+{
++++++++return+sumSoFar;
++++}
++++return+sumRemaining(remaining+%2B+1,+count+-+1,+sumSoFar+%2B+remaining[0]);
}
printf("duplicate+is+%25d",+sumRemaining(array,+1001,+0)+-+500500);|314254|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|Q|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|I|3|-4|5|6|7|S|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|T|8|@]|9|@]|A|$]]|$1|L|3|M|5|D|7|U|8|@]|9|@]|A|$E|F]]|$1|N|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|O|$]]

Do arguments and callstacks count as auxiliary storage?



<pre class="lang-c prettyprint-override"><code>int sumRemaining(int* remaining, int count) {
 if (!count) {
 return 0;
 }
 return remaining[0] + sumRemaining(remaining + 1, count - 1);
}
</code></pre>



<pre class="lang-c prettyprint-override"><code>printf("duplicate is %d", sumRemaining(array, 1001) - 500500);
</code></pre>

<hr>

Edit: tail call version

<pre class="lang-c prettyprint-override"><code>int sumRemaining(int* remaining, int count, int sumSoFar) {
 if (!count) {
 return sumSoFar;
 }
 return sumRemaining(remaining + 1, count - 1, sumSoFar + remaining[0]);
}
printf("duplicate is %d", sumRemaining(array, 1001, 0) - 500500);
</code></pre>

blocks|key|314308|text|n+=+1000
s+=+sum(GivenList)
r+=+str(n/2)
duplicate+=+int(+r+%2B+r+)+-+s|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|314309|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s
</code></pre>

blocks|key|312233|text|public+static+void+main(String[]+args)+{
++++int+start+=+1;
++++int+end+=+10;
++++int+arr[]+=+{1,+2,+3,+4,+4,+5,+6,+7,+8,+9,+10};
++++System.out.println(findDuplicate(arr,+start,+end));
}

static+int+findDuplicate(int+arr[],+int+start,+int+end)+{

++++int+sumAll+=+0;
++++for(int+i+=+start;+i+<=+end;+i%2B%2B)+{
++++++++sumAll+%2B=+i;
++++}
++++System.out.println(sumAll);
++++int+sumArrElem+=+0;
++++for(int+e+:+arr)+{
++++++++sumArrElem+%2B=+e;
++++}
++++System.out.println(sumArrElem);
++++return+sumArrElem+-+sumAll;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|312234|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre class="lang-java prettyprint-override"><code>public static void main(String[] args) {
 int start = 1;
 int end = 10;
 int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10};
 System.out.println(findDuplicate(arr, start, end));
}

static int findDuplicate(int arr[], int start, int end) {

 int sumAll = 0;
 for(int i = start; i &lt;= end; i++) {
 sumAll += i;
 }
 System.out.println(sumAll);
 int sumArrElem = 0;
 for(int e : arr) {
 sumArrElem += e;
 }
 System.out.println(sumArrElem);
 return sumArrElem - sumAll;
}
</code></pre>

blocks|key|314327|text|public+int+duplicateNumber(int[]+A)+{
++++int+count+=+0;
++++for(int+k+=+0;+k+<+A.Length;+k%2B%2B)
++++++++count+%2B=+A[k];
++++return+count+-+(A.Length+*+(A.Length+-+1)+>>+1);
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|314328|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre class="lang-cs prettyprint-override"><code>public int duplicateNumber(int[] A) {
 int count = 0;
 for(int k = 0; k &lt; A.Length; k++)
 count += A[k];
 return count - (A.Length * (A.Length - 1) &gt;&gt; 1);
}
</code></pre>

blocks|key|312219|text|一个三角形数T(+n+)是从1到n的n个自然数之和。它可以表示为n(n%2B1)/2。因此，知道在给定的1001个自然数中，只有一个数是重复的，你可以很容易地将所有给定的数相加并减去T(1000)。结果将包含此副本。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|312220|对于一个三角形数T(n)，如果n是10的任何幂，也有一个很好的方法来求这个T(n)，基于基数10的表示：|312221|n+=+1000
s+=+sum(GivenList)
r+=+str(n/2)
duplicate+=+int(+r+%2B+r+)+-+s|code-block|syntax|javascript|312222|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

A triangle number T(n) is the sum of the n natural numbers from 1 to n. It can be represented as n(n+1)/2. Thus, knowing that among given 1001 natural numbers, one and only one number is duplicated, you can easily sum all given numbers and subtract T(1000). The result will contain this duplicate.

For a triangular number T(n), if n is any power of 10, there is also beautiful method finding this T(n), based on base-10 representation:

<pre><code>n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s
</code></pre>

blocks|key|3051572|text|基于XORing连续值性质的Fraci答案的改进|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3051573|int+result+=+xor_sum(N);
for+(i+=+0;+i+<+N%2B1;+i%2B%2B)
{
+++result+=+result+%5E+array[i];
}|code-block|syntax|javascript|3051574|其中：|3051575|//+Compute+(((1+xor+2)+xor+3)+..+xor+value)
int+xor_sum(int+value)
{
++++int+modulo+=+x+%25+4;
++++if+(modulo+==+0)
++++++++return+value;
++++else+if+(modulo+==+1)
++++++++return+1;
++++else+if+(modulo+==+2)
++++++++return+i+%2B+1;
++++else
++++++++return+0;
}|3051576|或者在伪代码/数学语言f(n)中定义为(优化)：|3051577|if+n+mod+4+=+0+then+X+=+n
if+n+mod+4+=+1+then+X+=+1
if+n+mod+4+=+2+then+X+=+n%2B1
if+n+mod+4+=+3+then+X+=+0|3051578|并且在规范形式中f(n)是：|3051579|f(0)+=+0
f(n)+=+f(n-1)+xor+n|3051580|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|Y|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|10|8|@]|9|@]|A|$]]|$1|Q|3|R|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

Improvement of Fraci's answer based on the property of XORing consecutive values:



<pre class="lang-c prettyprint-override"><code>int result = xor_sum(N);
for (i = 0; i &lt; N+1; i++)
{
 result = result ^ array[i];
}
</code></pre>

Where:

<pre class="lang-c prettyprint-override"><code>// Compute (((1 xor 2) xor 3) .. xor value)
int xor_sum(int value)
{
 int modulo = x % 4;
 if (modulo == 0)
 return value;
 else if (modulo == 1)
 return 1;
 else if (modulo == 2)
 return i + 1;
 else
 return 0;
}
</code></pre>

Or in pseudocode/math lang f(n) defined as (optimized):

<pre class="lang-c prettyprint-override"><code>if n mod 4 = 0 then X = n
if n mod 4 = 1 then X = 1
if n mod 4 = 2 then X = n+1
if n mod 4 = 3 then X = 0
</code></pre>

And in canonical form f(n) is:

<pre class="lang-c prettyprint-override"><code>f(0) = 0
f(n) = f(n-1) xor n
</code></pre>

blocks|key|311391|text|我支持将所有元素相加，然后从中减去所有索引的总和，但如果元素的数量非常大，这将不起作用。也就是说，它会导致一个整数溢出！所以我设计了这个算法，它可能会在很大程度上减少整数溢出的机会。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|311392|+++for+i=0+to+n-1
++++++++begin:++
++++++++++++++diff+=+a[i]-i;
++++++++++++++dup+=+dup+%2B+diff;
++++++++end
+++//+where+dup+is+the+duplicate+element..|code-block|syntax|javascript|311393|但是通过这种方法，我将无法找出重复元素所在的索引！|311394|为此，我需要另一次遍历数组，这是不可取的。|311395|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

I support the addition of all the elements and then subtracting from it the sum of all the indices but this won't work if the number of elements is very large. I.e. It will cause an integer overflow! So I have devised this algorithm which may be will reduce the chances of an integer overflow to a large extent.

<pre><code> for i=0 to n-1
 begin: 
 diff = a[i]-i;
 dup = dup + diff;
 end
 // where dup is the duplicate element..
</code></pre>

But by this method I won't be able to find out the index at which the duplicate element is present! 

For that I need to traverse the array another time which is not desirable.

blocks|key|3051682|text|我对问题2的回答是：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3051683|求1-(到)+N中数字的和和乘积，比如SUM，PROD。|offset|length|style|CODE|3051684|从1-+N-+x+-y中找出数字的和和乘积，(假设x，y缺失)，比如mySum，myProd，|3051685|因此：|3051686|SUM+=+mySum+%2B+x+%2B+y;
PROD+=+myProd*+x*y;|code-block|syntax|javascript|3051687|3051688|x*y+=+PROD/myProd;+x%2By+=+SUM+-+mySum;|3051689|如果解这个方程，我们就可以找到x，y。|3051690|entityMap^0|0|J|3|N|4|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Y|8|@$D|Z|E|10|F|G]|$D|11|E|12|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|13|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|14|8|@]|9|@]|A|$]]|$1|L|3|M|5|N|7|15|8|@]|9|@]|A|$O|P]]|$1|Q|3|K|5|6|7|16|8|@]|9|@]|A|$]]|$1|R|3|S|5|N|7|17|8|@]|9|@]|A|$O|P]]|$1|T|3|U|5|6|7|18|8|@]|9|@]|A|$]]|$1|V|3|-4|5|6|7|19|8|@]|9|@]|A|$]]]|W|$]]

My answer to question 2:

Find the sum and product of numbers from 1 -(to) N, say <code>SUM</code>, <code>PROD</code>.

Find the sum and product of Numbers from 1 - N- x -y, (assume x, y missing), say mySum, myProd,

Thus:

<pre><code>SUM = mySum + x + y;
PROD = myProd* x*y;
</code></pre>

Thus:

<pre><code>x*y = PROD/myProd; x+y = SUM - mySum;
</code></pre>

We can find x,y if solve this equation.

blocks|key|3265410|text|在aux版本中，首先将所有值设置为-1，然后在迭代时检查是否已将值插入aux数组。如果不是(则值必须为-1+)，则插入。如果你有一个副本，这是你的解决方案！|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3265411|在没有aux的情况下，从列表中检索一个元素，并检查列表的其余部分是否包含该值。如果它包含，那么在这里您已经找到了它。|3265412|private+static+int+findDuplicated(int[]+array)+{
++++if+(array+==+null+%7C%7C+array.length+<+2)+{
++++++++System.out.println("invalid");
++++++++return+-1;
++++}
++++int[]+checker+=+new+int[array.length];
++++Arrays.fill(checker,+-1);
++++for+(int+i+=+0;+i+<+array.length;+i%2B%2B)+{
++++++++int+value+=+array[i];
++++++++int+checked+=+checker[value];
++++++++if+(checked+==+-1)+{
++++++++++++checker[value]+=+value;
++++++++}+else+{
++++++++++++return+value;
++++++++}
++++}
++++return+-1;
}

private+static+int+findDuplicatedWithoutAux(int[]+array)+{
++++if+(array+==+null+%7C%7C+array.length+<+2)+{
++++++++System.out.println("invalid");
++++++++return+-1;
++++}
++++for+(int+i+=+0;+i+<+array.length;+i%2B%2B)+{
++++++++int+value+=+array[i];
++++++++for+(int+j+=+i+%2B+1;+j+<+array.length;+j%2B%2B)+{
++++++++++++int+toCompare+=+array[j];
++++++++++++if+(value+==+toCompare)+{
++++++++++++++++return+array[i];
++++++++++++}
++++++++}
++++}
++++return+-1;
}|code-block|syntax|javascript|3265413|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

In the aux version, you first set all the values to -1 and as you iterate check if you have already inserted the value to the aux array. If not (value must be -1 then), insert. If you have a duplicate, here is your solution!

In the one without aux, you retrieve an element from the list and check if the rest of the list contains that value. If it contains, here you've found it.

<pre><code>private static int findDuplicated(int[] array) {
 if (array == null || array.length &lt; 2) {
 System.out.println("invalid");
 return -1;
 }
 int[] checker = new int[array.length];
 Arrays.fill(checker, -1);
 for (int i = 0; i &lt; array.length; i++) {
 int value = array[i];
 int checked = checker[value];
 if (checked == -1) {
 checker[value] = value;
 } else {
 return value;
 }
 }
 return -1;
}

private static int findDuplicatedWithoutAux(int[] array) {
 if (array == null || array.length &lt; 2) {
 System.out.println("invalid");
 return -1;
 }
 for (int i = 0; i &lt; array.length; i++) {
 int value = array[i];
 for (int j = i + 1; j &lt; array.length; j++) {
 int toCompare = array[j];
 if (value == toCompare) {
 return array[i];
 }
 }
 }
 return -1;
}
</code></pre>

I recently came across a question somewhere:

<blockquote>
 Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
</blockquote>

What I am interested in to know is the second part, i.e., without using auxiliary storage. Do you have any idea?

How to find a duplicate element in an array of shuffled consecutive integers?

我最近在某个地方遇到了一个问题：假设您有一个包含1001个整数的数组。这些整数的顺序是随机的，但您知道每个整数都在1到1000 (包括1和1000)之间。此外，每个数字在数组中只出现一次，但有一个数字出现两次。假设您只能访问数组的每个元素一次。描述一种查找重复数的算法。如果你在你的算法中使用了辅助存储，你能找到一个不需要它的算法吗？我感兴趣的是second part，即不使用辅助存储的。你有什么想

问如何在经过混洗的连续整数数组中找到重复的元素？
EN

回答 17

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在经过混洗的连续整数数组中找到重复的元素？EN

回答 17

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在经过混洗的连续整数数组中找到重复的元素？
EN