据说是微软的考题(出自<<世界500强试题>>)

Question

假设你有一个用1001个整数组成的数组,这些整数是任意排列的,但是你知道所有的数都在1到1000之间(包括1000).此外,除一个数出现2次外,其他数字都只出现一次.你只能对这数组做一次处理,用一种算法找出重复的那个数.如果你在运算中使用了辅助的存储方式,那么你能找到不用这种方式的算法吗?

Answer 1

申请辅助数组b，b[i]表示i在给定数组a的下标
把b清为－1
扫描数组a，如果b[a[i]] = -1表示a[i]刚刚出现，令b[a[i]] = i
负责，输出这个重复的数
C＋＋代码如下：
void find(int a[10001])
{
int b[10001];
int i;
for(i = 0;i < 10001;i++) b[i] = -1;
for(i = 0;i < 10001;i++)
{
if(b[a[i]] != -1) cout << "the index of the repeat number is " << i << " " << endl;
b[a[i]] = i;
}
} 
不过要那么大的辅助空间，如果不用辅助空间，我就想不到

Answer 2

上面的输出语句应该改成
if(b[a[i]] != -1) 
    cout << "the index of the repeat number is " << i << " and " << b[a[i]]<< endl;

Answer 3

用辅助储存：考虑hash表方式不用辅助储存：考虑置换方式

Answer 4

diaodou(凋豆) 太狠了,一个辅助存储变量都不能使用,你还一口气用了1001个!

Answer 5

循环调换位置法（暂时这样命名一下^O^）：DELPHI实现
A[0..1000]；  表示存贮的数据数组
var
    i:=0;  //循环变量
begin
    while i<=1000 do
    begin
        if A[i] <> i+1 then
        begin
             if A[i]<i+1 then
                 showmessage('出现两次的数字是：'+inttostr(A[i]);
             //以下三行是，交换两个数字的位置！ 
             A[i]=A[A[i]]+A[i];
             A[A[i]]:=A[i]-A[A[i]];
             A[i]:=A[i]-A[A[i]];
        end
        else
            inc(i);
    end;
end;

Answer 6

sunware，你的意思是不是只能用些循环变量，不用其他任何变量就可以求出来？
没有可能
题目的意思，辅助存储方式就是说数组啊，然后说不用数组怎么办，我的理解

Answer 7

第一步，已知从1累加到1000的结果是500500，（1＋2＋3＋...＋1000＝500500）
第二步，程序从数据中第一项取值，加上第二项的值、第三项的值、...、第1001项的值，得到结果N
第三步，计算N－500500＝XX是重复的那个数。---------不会这么简单吧？

Answer 8

以上代码有点问题：找到重复数字后没有终止程序：
if A[i]<i+1 then
    showmessage('出现两次的数字是：'+inttostr(A[i]);
以上两行代码改为：
if A[i]<i+1 then
begin
    showmessage('出现两次的数字是：'+inttostr(A[i]);
    break;
end;

Answer 9

jinjazz(近身剪*10年磨一贴) 
高,

Answer 10

第一步，已知从1累加到1000的结果是500500，（1＋2＋3＋...＋1000＝500500）
第二步，程序从数据中第一项取值，加上第二项的值、第三项的值、...、第1001项的值，得到结果N
第三步，计算N－500500＝XX是重复的那个数。---------不会这么简单吧？
---------------------------------------------------------比较同意你的算法,,只要能解决问题就行

Answer 11

var
  v, i: Integer;
begin
  v := 0;
  for i:=Low(TheArray) to High(TheArray) do
    Inc(v, TheArray[i]);
  ShowMessage('重复的那个数字是：' + IntToStr(500500-v));
end;

Answer 12

diaodou(凋豆) 
你用了两个数组.一个是a[1..1001],另一个是b[1..1001].a是允许的,b是不允许的. noever_jj() 
排序是不允许的.因为排序算法会多次遍历这个数组,同时也可能会使用辅助储存变量.

Answer 13

SeaWave(NoSound)的方法确实高明。但是要根据题目要求做一下变动更好！for i:=0 to 1000 do
begin
    A[0]:=A[i]+1-i;
end;
最后结果就是：A[0]+1001这值就是重复的那个数字了！

Answer 14

to jinjazz，love_birds
还要求出那个数的位置的吧

Answer 15

又错了：应该是：
SeaWave(NoSound)的方法确实高明。但是要根据题目要求做一下变动更好！for i:=0 to 1000 do
begin
    A[0]:=A[i]-(i+1);
end;
最后结果就是：A[0]+1001这值就是重复的那个数字了！

Answer 16

聪明者,jinjazz(近身剪*10年磨一贴)也!

Answer 17

diaodou(凋豆) 要是找位置，重复数字有两个，是不是把两个位置都找出来？他只问是哪个数？没说这两个数分别在什么位置！

Answer 18

>>晕死，什么叫找出那个数？
>>当然要告诉是哪个位置啦
--------用一种算法找出重复的那个数这句话很容易理解的吧

Answer 19

Love_birds(蝎子王) 的想法和我的差不多.
我是这样写的:procedure SWap(var a,b : integer);
begin
a := a + b;
b := a - b;
a := a - b;
end;procedure GetTheNumber;
var
i : integer;
begin
i := 0;
repeat
   if Numbers[i] <> i then begin
      if Numbers[Numbers[i]] = Numbers[i] then begin
         ShowMessage('The numbers is: ' + InttoStr(Numbers[i]));
         Break;
      end else
         Swap(Numbers[i],Numbers[Numbers[i]]);
   end else
      Inc(i);
until( i >= 1000);
end;

Answer 20

love_birds,我不是找出两个位置来了吗？如果只是求什么数重复，那么这个是很简单，一点意思都没有，晕死

Answer 21

如果求位置,diaodou(凋豆)用hash的方法是最快的,不用辅助空间是不可能的
比较总要有源数据和目标数据,不用辅助,就得和自己比,那必然要多次操作.想只遍历一次就得把已检索信息另外保存

Answer 22

昨天仔细一想,其实求和的做法是不妥当的。因为从题目的条件来看,程序的运行环境应是内存极度匮乏，在这种情况下，整形应判断为短整形（signed 16-bit或unsigned 16-bit）。这样，求和结果为500500，超过了短整形的上限了。所以求和是求不出来的。

Answer 23

回复人： jinjazz(近身剪*10年磨一贴) 求和不就知道了高!!只能是佩服.