面试题3-数组中的重复数字

旧城等待， 2022-03-12 04:55 188阅读 0赞

# 一、题目 #

###         在长度为n的数组中，所有的元素都是0到n-1的范围内。 数组中的某些数字是重复的，但不知道有几个重复的数字，也不知道重复了几次，请找出任意重复的数字。 例如，输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出为2或3。 ###

# 二、题目分析 #

###         1、可以利用哈希表来解决该问题。首先创建一个辅助数组，在辅助数组中存储所有元素的出现次数。然后遍历辅助数组，返回所有值大于1的位置，这些位置就是所有重复的数字。 ###

###         2、可以采用重排数组的方式。从头到尾扫描数组中的每个数字，当扫描到下标为i的数字时，首先比较这个数字m是不是等于i。若是，则接着扫描下一个数字；若不是，则再拿它和第m个数字比较。若它和第m个数字相等，就找到了一个重复数字；若不相等，则把第i个数字和第m个数字交换。接下来再重复比较、交换。 ###

# 三、代码实现 #

### 方法一： ###

//方法一：采用哈希表
    vector<int> sameNumber1(int a[],int len) {
    	if (a == nullptr || len <= 0) throw "error";//如果数组不存在或长度小于等于0
    	for (int i = 0; i < len; ++i) {//如果数组元素的范围不在[0,len-1]之间
    		if (a[i] < 0 || a[i] > len - 1) throw "error";
    	}
    	int* b = new int[len + 1];//创建临时数组作为哈希表
    	vector<int> vec;//创建输出的向量，存储重复的元素
    	for (int i = 0; i < len + 1; ++i) {//初始化哈希表
    		b[i] = 0;
    	}
    	for (int i = 0; i < len; ++i) {//哈希表中存储数组元素的重复次数
    		b[a[i]]++;
    	}
    	for (int i = 0; i < len + 1; ++i) {
    		if (1 < b[i]) {//将哈希表中重复次数大于1的位置保存在向量中
    			vec.push_back(i);
    		}
    	}
    	return vec;
    }

### 方法二： ###

//方法二：重排数组(只是判断是否存在重复数字)
    bool sameNumber2(int a[], int len) {
    	if(a == nullptr || len <= 0){//如果数组不存在或长度小于等于0
    		return false;
    	}
    	for (int i = 0; i < len; ++i) {//如果数组元素的范围不在[0,len-1]之间
    		if (a[i] < 0 || a[i] > len - 1) {
    			return false;
    		}
    	}
    	for (int i = 0; i < len; ++i) {//循环
    		while (a[i] != i) {//若a[i]不等于等于i
    			if (a[i] == a[a[i]]) {//且a[i]等于a[a[i]]
    				return true;//此时存在重复元素返回true
    			}
    			else {//若a[i]等于a[a[i]]，则交换两个元素的位置
    				int temp = a[i];
    				a[i] = a[temp];
    				a[temp] = temp;
    			}
    		}
    	}
    }