数组中重复的数字

题目：

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

例如：

算法1：

将数组排序，排完序之后遍历。时间复杂度O(nlogn),空间复杂度O(n)

c语言

int Cmp_int(const void* vp1, const void* vp2)
{
    return *(int*)vp1 - *(int*)vp2;
}
int findRepeatNumber1(int* nums, int numsSize)
{
    qsort(nums,numsSize,sizeof(int),Cmp_int);//调用排序算法,需要引用stdlib.h
    for (int i = 0; i+1 < numsSize; i++)
    {
        if (nums[i] == nums[i + 1])
            return nums[i];
    }
    return -1;
}

c++:

c++跟c语言类似，只不过c++库里有sort函数，我们可以使用这个函数来排序，然后遍历，查找连续两个相同的即可

算法2：

利用哈希表存储（本题范围刚好在0～n-1内，arr[i]对应的就是i），时间复杂度O(n),空间复杂度O(n)

C语言

int findRepeatNumber(int* nums, int numsSize)
{
    int* arr = (int*)malloc(numsSize * sizeof(int));
    int i;
    int m;
    for (i = 0; i < numsSize; i++)
        arr[i] = -1;//-1表示无效值
    for (i = 0; i < numsSize; i++)
    {
        m = nums[i];
        if (arr[m] != -1)//找到了
        {
            free(arr);
            return m;
        }
        arr[m] = m;
    }
    free(arr);
    return -1;//没有重复的
}

C++:

int FindReatNumber(vector<int> nums, int numSize)
{
	vector<int> v(numSize,0);
	
	for (int i = 0; i < numSize; i++)
	{
		v[nums[i]]++;
	}
	for (int i = 0; i < numSize; i++)
	{
		if (v[i] >= 2)
			return i;
	}
}

c++我们使用vector数组将其全部重置为0,然后遍历，nums[i]对应的是遍历的时候i这个位置对应的数字，然后将其放在对应的v[nums[i]]的位置上,即这个数字++;

算法3:

数据归位：时间复杂度O(n),空间复杂度O(1)

int findRepeatNumber3(int* nums, int numsSize) //O(n),O(1)
{
    int m;
    for (int i = 0; i < numsSize; i++)
    {
        while (nums[i] != i)//当前位置,存放的不是当前数据,交换
        {
            m = nums[i];
            if (m == nums[m])//找到了
                return m;
            nums[i] = nums[m];
            nums[m] = m;
        }
    }
    return -1;
}

int main()
{
    int nums[] = { 2, 3, 1, 0, 2, 5, 3 };
    printf("%d\n", findRepeatNumber(nums,sizeof(nums)/sizeof(nums[0])));

    return 0;
}