題目描述

在一個(gè)長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。

示例 ：
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3

思路分析

首先想到的是暴力法—兩個(gè)for循環(huán)實(shí)現(xiàn)，缺點(diǎn)很明顯：用時(shí)過多。再進(jìn)一步可以先排序數(shù)組然后一次for循環(huán)，容易找出所有的重復(fù)元素以及重復(fù)的次數(shù)，用時(shí)依舊較長。

我們考慮如果每個(gè)數(shù)字都置出現(xiàn)一次，那么此時(shí)是最完美的，每一個(gè)下標(biāo)i對應(yīng)元素numbers[i]，也就是說我們對于數(shù)組中的每個(gè)元素numbers[i]都把它放在自己應(yīng)該在的位置上numbers[numbers[i]]上, 如果我們發(fā)現(xiàn)有兩個(gè)元素想往同一個(gè)位置上放的時(shí)候，說明此元素必然重復(fù)

即如下的過程：

• 如果numbers[i] == i, 那么我們認(rèn)為number[i]這個(gè)元素是在自己的位置上的

• 否則的話,numbers[i]這個(gè)元素就應(yīng)在numbers[numbers[i]]這個(gè)位置上, 于是交換numbers[i]和numbers[numbers[i]]。

• 重復(fù)操作1, 直到number[i]== i, 則繼續(xù)操作下一個(gè)位置的元素, 或者numbers[i] == numbers[numbers[i]，元素重復(fù)。

代碼實(shí)現(xiàn)

//#include <stdlib.h>   //C語言
#include<iostream>
using namespace std;

//2020.05.22
int findRepeatNumber(int* nums, int numsSize) {
	//此題無須增加對數(shù)組為空、元素個(gè)數(shù)為0、元素越界情況的判斷
	for (int i = 0; i < numsSize; i++) {
		//如果元素位置不對，則交換
		while (nums[i] != i) {
			//交換前檢查是否相等
			if (nums[i] == nums[nums[i]])
				return nums[i];
			int temp = nums[i];
			nums[i] = nums[temp];
			nums[temp] = temp;
		}
	}
	return -1;
}

int main()
{
	int a[] ={2, 3, 1, 0, 2, 5, 3};

	findRepeatNumber(a,7);
	printf("%d",findRepeatNumber(a,7));
	return 0;
}