栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

面试题3:数组中重复的数字【Java实现】

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

面试题3:数组中重复的数字【Java实现】

1. 数组中重复的数字 题目一:找出数组中重复的数字

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

输入:[2,3,1,0,2,5,3]
输出:2或3
//数组长度为7,重复的只有2和3,因此任意输出一个结果都是正确的    
思路①
  • 利用长度为n的数组arr记录某个数字的出现次数,数组下标与数字一一对应【如数字0就由arr[0]记录其出现的次数】,当统计的个数超过1时就将此下标输出。
  • 时间复杂度O(n),空间复杂度O(n)
代码实现
public static void duplicate(int numbers[]) {
		int n = numbers.length;
		int arr[] = new int[n];
		for (int i = 0; i < n; i++) {
			int index=numbers[i];	//当前数字出现次数信息存储在arr[index]
			arr[index]++;
			if(arr[index]==2) {	//当次数等于2时,说明index就是重复数
				System.out.println(index);
				break;
			}
		}
	}
思路②
  • 由于数组中的数字都处于0~n-1范围内,如果数组中没有重复的数,那么当数组排序之后数组i将出现在下标为i的位置。
  • 因此我们的新思路为“将每个数摆到属于自己的地方”
    • 首先比较这个数字是不是等于当前扫描到的下标,如果是则说明其处于正确位置,继续往后扫描;如果不是,则将此数字送到属于自己的下标位置。
    • 若此时发现下标位置已被正确占领,则说明此数字重复,输出此数;反之则进行对调,再重复进行判断。
  • 时间复杂度O(n),空间复杂度O(1)
代码实现
public static void duplicate(int numbers[]) {
		int n = numbers.length;
		int temp;
		for (int i = 0; i < n; i++) {
			while (numbers[i] != i) {// 此时说明当前数字处于错误位置
				int index = numbers[i]; // 正确的位置下标为index
				if (numbers[index] == index) {
					// 正确的位置已经名花有主,说明这个位置存放的数就是重复的
					System.out.println(index);
					i=n;	//使函数跳出for循环		
				} else {
					temp = numbers[index];
					numbers[index] = numbers[i];
					numbers[i] = temp;
				}
			}
		}
	}
题目二:不修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。

输入:[2,3,5,4,3,2,6,7]
输出:2或3
//数组长度为8,重复的只有2和3,因此任意输出一个结果都是正确的  
思路①
  • 可参考题目一中的思路①,用辅助数组对各个数字的出现次数进行统计。
思路②
  • 在1~n的范围里只有n个数字,而数组空间有n+1个,所以一定有重复数
  • 我们可以采用二分法的思想,把1~n的数字从中间的数字m分为两部分,前面一半为1~m,后面一半为m+1~n。如果数组里1~m的数字个数超过m,则重复的数字肯定会出现在1~m这个区间里【但这并不代表另一个区间就没有重复数字,只是题目仅要求我们找出任意重复数字即可】,否则出现在另一个区间里。
  • 通过不断缩小区间范围,最后我们确定下一个重复的数字
  • 时间复杂度O(nlogn),空间复杂度O(1)
代码实现
public static int duplicate(int numbers[]) {
		int n = numbers.length-1 ; // 数组内存放数字范围1~n,数组空间有n+1个,下标从0到n
		int left = 1, right = n;
		while (left <= right) {
			int m = (left + right) / 2; // left~right的中间数
			// [left,m]范围的数字在数组中出现的次数
			int count = getCountNum(numbers, left, m);
			if (left == right) { // 说明此时二分已经将范围缩小到最后一个数字
				if (count == 1) {
					// 此时说明当前数字在数组中出现的次数为1次,整个数组没有重复数
					break;
				} else {
					// 此时说明最终定位到的就是重复数
					return left;
				}
			}
			if (count > m - left + 1) {
				// [left,m]范围数字出现的次数多于这个范围数字一一对应时的数目
				// 此时在此范围肯定出现了重复数
				right = m;
			} else {
				// 在另一个范围出现了重复数
				left = m + 1;
			}
		}
		return -1;
	}

	// 返回[left,right]范围的数字在numbers[]数组中出现的次数
	public static int getCountNum(int numbers[], int left, int right) {
		int count = 0;
		for (int i = 0; i < numbers.length; i++) {
			if (numbers[i] >= left && numbers[i] <= right) {
				count++;
			}
		}
		return count;
	}

题目虽然看上去不难,但是其中细节还是挺多的,建议手动进行实现!

题目来源于《剑指Offer:名企面试官精讲经典编程题(第2版)》

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/930651.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号