Ex3 找出数组中重复的数字

题目

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例 输入： nums = [2, 3, 1, 0, 2, 5, 3] 输出： 2 或 3

问题分析

题目中最有意思的地方在于数组的长度为n，且所有的数字都在0~n-1的范围内。在正常情况下，数组的长度为4，nums = [0, 1, 2, 3]（或者以上几个数字的一种全排列的形式），一个不多一个不少。如果有一个重复或几个重复的话，则肯定有一个数是没有的。假设1是重复的，举例：nums = [0, 1, 1, 3]，2就没有了。

解题思路

将nums中的各个项num，放到相应的位置nums[num]。循环下去，如果在没有重复的情况下，最后肯定会得到这个结果：nums = [0, 1, 2, 3,]。但是，在有重复的情况下，势必会出现nums[num] = num的情况。如：nums = [0, 1, 1, 3]，将第二个出现的1放到索引为1的过程中时，发现索引为1处已经是1了，所以就可以表明nums出现了重复，重复数字为1。 由于本题只要求得到1个重复的数字，不需要得到重复的数字的个数或重复了几次等结果。所以结果想到这里就可以了。

代码

int
findRepeatNumber (int *nums, int numsSize)
{
  for (int i = 0; i < numsSize; ++i)
    {
      while (nums[i] != i)
        {
          if (nums[nums[i]] == nums[i])
            {
              return nums[i];
            }
          int tmp = nums[i];
          nums[i] = nums[tmp];
          nums[tmp] = tmp;
        }
    }
    return nums[numsSize - 1];
}

结果

执行结果：

通过

执行用时：44 ms, 在所有 C 提交中击败了63.20%的用户

内存消耗：10.1 MB, 在所有 C 提交中击败了62.55%的用户

一般吧，算是及格了!