[开发测试]数组中重复的数字（数组元素个数等于数组长度）

1、题目描述：
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7,的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数组2或者3。
注：该方式
2、测试用例

• 长度为n的数组中包含一个或多个重复的数字
• 数组中不包含重复的数字
• 无效输入测试用例（输入空指针；长度为n的数组中包含0~n-1之外的数字）

3、解答思路
思路一：两层遍历，暴力解法，一个元素一个元素遍历是否等于前面的元素
复杂度分析：时间复杂度O(N^2)，空间复杂度O(1)

#include <stdio.h>

int Find_Repeat_Num(int *arr,int size)  
{
	int i,j;
	if(arr == NULL || size < 2)
	{
    	return;
    }
    printf("重复的数字是:\n");
  	for(i=0;i<size-1;i++)
  	{
  		for(int j=i+1;j<size;j++)
  		{
        	if(arr[i] == arr[j])
        	{
            	printf("%d\n", arr[i]);
            	break;
            }
        }
    }
    return;
}

int main()
{
	int arr[] = {1,2,3,4,2};
  	int size = sizeof(arr)/sizeof(int);
    Find_Repeat_Num(arr,size);
  	return 0;
}

思路二：修改输入输入数组
将输入数组进行重新排序，从头到尾进行遍历。假设a[i]对应的数值为m，
首先比较m是否等于i，如果等于i，则接着扫描下一个数字。如果不等于，就再比较m是否等于a[m]，如果等于，说明m就是其中一个重复数字。如果不等于，就将a[i]和a[m]交换，这样m就放在了自己对应的下标处。然后再重复以上操作即可。
复杂度分析：时间复杂度O(nlogn)，空间复杂度O(1)
代码如下：

#include <stdio.h>

int Find_Repeat_Num(int *arr,int size) 
{
	int i;
  	int t;
	if(arr == NULL || size < 2)
	{
    	return;
    }
    printf("重复的数字是:\n");
  	for(i=0;i<size;i++)
  	{
    	if(arr[i]<0 || arr[i]>=size)
      	{
      		return;
      	}
      	else
      	{
    		while(arr[i] != i)//判断数组中的数字是否对应其下标
    		{
      			if(arr[i] == arr[arr[i]])//判断
      			{
        			printf("%d\n", arr[i]);
        			break;
        		}
        		else
        		{
      				int t = arr[i];
      				arr[i] = arr[t];
      				arr[t] = t;
      			}
      		}
      	}
    }
  return;
}

int main()
{
	int arr[] = {1,2,3,4,2};
  	int size = sizeof(arr)/sizeof(int);
    Find_Repeat_Num(arr,size);
  	return 0;
}

思路三：哈希表遍历法
个人暂时没有了解哈希表，暂时不在此做介绍，后期会更新哈希表的解法