日期:2014-05-18  浏览次数:20785 次

这个面试题算法给出答案貌似是错的?
两个数组 [n] [m] n>m 第一个数组的数字无序排列 第二个数组为空 取出第一个数组的最小值 放到第二个数组中第一个位置, 依次类推. 不能改变A数组,不能对之进行排序,也不可以倒到别的数组中。
这是他的答案:  
  int[] a = { -20, 9, 7, 37, 38, 69, 89, -1, 59, 29, 0, -25, 39, 900, 22, 13, 55 };

  int[] b = new int[10];

  int intTmp = a[0], intMaxNum;

  for (int i = 0; i < a.Length; i++)

  {

  intTmp = a[i] > intTmp ? a[i] : intTmp;

  }

  intMaxNum = intTmp;

  for (int j = 0; j < b.Length; j++)

  {

 

  for (int i = 0; i < a.Length; i++)

  {

  if (j == 0)

  intTmp = a[i] < intTmp ? a[i] : intTmp;

  else

  {

  if (a[i] > b[j - 1])

  intTmp = a[i] < intTmp ? a[i] : intTmp;

  }

  }

  b[j] = intTmp;

  intTmp = intMaxNum;

  }

  foreach (int bb in b)

  {

  Console.WriteLine(bb);

 

  }

  Console.ReadLine();

当A数组中有重复的数字时,明显就不对了,请问这个算法要怎么写?

------解决方案--------------------
你说的不错。这个算法是错误的,有重复值情况下就会出错,下面的代码运行结果正确:
C# code

//为了便于说明,数组里加了个重复的数字9
int[] a = { 9, -20, 9, 7, 37, 38, 69, 89, -1, 59, 29, 0, -25, 39, 900, 22, 13, 55 };

            int[] b = new int[10];
            List<int> positions = new List<int>();//我新加的,记录最小值的位置

            int intTmp = a[0], intMaxNum;

            for (int i = 0; i < a.Length; i++)
            {

                intTmp = a[i] >= intTmp ? a[i] : intTmp;//大于号改成大于等于

            }

            intMaxNum = intTmp;


            for (int j = 0; j < b.Length; j++)
            {
                int tpos = -1;//记录最小值的位置
                for (int i = 0; i < a.Length; i++)
                {

                    if (j == 0)
                    {
                        if (a[i] <= intTmp)
                        {//改写了,小于号改成小于等于
                            tpos = i;//关键是记录最小值的下标
                            intTmp = a[i];
                        }
                    }
                    else
                    {

                        if (positions.Contains(i) == false && a[i] >= b[j - 1])
                        {//改写了,检查最小值的下标是否已记录
                            if (a[i] <= intTmp)
                            {
                                tpos = i;
                                intTmp = a[i];
                            }
                        }
                    }
                }
                positions.Add(tpos);//把最小值的下标加入
                b[j] = intTmp;

                intTmp = intMaxNum;

            }

              foreach (int bb in b)

  {

  Console.WriteLine(bb);

 

  }

  Console.ReadLine();