题目描述
8 U3 c" l* _5 A" H' ~- |+ U

7 C+ E% ~  n4 t7 R, x1 q

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 ：
" q4 ?) [; d5 e. g7 B0 m- s& [输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
! C2 @4 Y6 r: M9 z
6 ^7 o3 @  a+ r1 e8 j4 P8 D思路分析

) {4 ^. E3 o8 b! M- i& m  h+ r

首先想到的是暴力法—两个for循环实现，缺点很明显：用时过多。再进一步可以先排序数组然后一次for循环，容易找出所有的重复元素以及重复的次数，用时依旧较长。

我们考虑如果每个数字都置出现一次，那么此时是最完美的，每一个下标i对应元素numbers，也就是说我们对于数组中的每个元素numbers都把它放在自己应该在的位置上numbers[numbers]上, 如果我们发现有两个元素想往同一个位置上放的时候，说明此元素必然重复

即如下的过程：

• 如果numbers == i, 那么我们认为number这个元素是在自己的位置上的

• 否则的话,numbers这个元素就应在numbers[numbers]这个位置上, 于是交换numbers和numbers[numbers]。

• 重复操作1, 直到number== i, 则继续操作下一个位置的元素, 或者numbers == numbers[numbers，元素重复。

  
  4 Z0 Q9 x( V5 v! e  G

代码实现


: W1 k; d2 O) {8 j7 s" Q" G" ^5 h//#include <stdlib.h>   //C语言
' }9 W5 W5 Z; Y  @7 G, u$ {, E9 Z
#include<iostream>
using namespace std;

//2020.05.22
% P5 q# N$ l4 E9 z( U6 C' Jint findRepeatNumber(int* nums, int numsSize) {
4 P: S) J2 C/ w& M        //此题无须增加对数组为空、元素个数为0、元素越界情况的判断
        for (int i = 0; i < numsSize; i++) {
' F4 d6 I9 ^, Y7 O6 ?& N+ q4 x& v; _                //如果元素位置不对，则交换
: o; O* ^$ @, H8 U& }! |  Q                while (nums != i) {
6 G- b; i+ A# T9 K3 F1 \+ x$ h                        //交换前检查是否相等
                        if (nums == nums[nums])
9 j: V8 q; S0 G                                return nums;
                        int temp = nums;
- J  b8 a8 a' G' c                        nums = nums[temp];
                        nums[temp] = temp;
( {  }7 Q( i6 M/ G                }
% d2 B* `! g, ^% \1 P% C        }
        return -1;
7 i4 _0 Y5 h* j6 T8 h: [}
4 @  R+ q" S; T* x& u; Z+ w
1 _/ H0 d" N2 p% n7 b/ hint main()
$ B( o- n3 S8 I$ W{
5 @  D" V/ g! J- |        int a[] ={2, 3, 1, 0, 2, 5, 3};

        findRepeatNumber(a,7);
( f4 D6 B# i% }; R        printf("%d",findRepeatNumber(a,7));
$ G' C6 j1 `- p- f        return 0;
}


运行结果