剑指offer_面试题：数组中重复的数字_Java实现

题目一：

具体三种实现方式参见代码：

import java.util.*;

public class First {
	public static void main(String[] args) {
		//处理输入
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] array = new int[n];
		for(int i = 0; i < n; i++)
			array[i] = in.nextInt();
		//WAY1：排序后遍历，时间复杂度O(nlgn)，不需要额外分配内存，空间复杂度O(1)
		Arrays.sort(array);
		for(int i = 0; i < n; i++) {
			if(array[i] == array[i+1]) {
				System.out.println("WAY1:	" + array[i]);
				break;
			}
		}
		//WAY2：哈希表，时间复杂度O(n)，需要额外分配内存，空间复杂度O(n)
		boolean[] hash = new boolean[n];
		for(int value: array) {
			if(hash[value]) {
				System.out.println("WAY2:	" + value);
				break;
			}
			else hash[value] = true;
		}
		//WAY3：扫描原数组，时间复杂度O(n)，不需要额外分配内存，空间复杂度O(1)
		//由于题目的设定，数组长度为n，所有数字在0~n-1范围内，那么若无重复，排序后下标值i应该与array[i]相等
		for(int i = 0; i < n; i++) {
			int value = array[i];
			if(value == i) continue;	//说明满足规律
			else {
				if(value == array[value]) {
					System.out.println("WAY3:	" + value);
					break;
				}
				else {
					array[i] = array[value];
					array[value] = value;
				}
			}
		}
	}
}

输入输出结果：

7
2 3 1 0 2 5 3
WAY1:    2
WAY2:    2
WAY3:    2
 

题目二：（要求不修改原数组）

import java.util.*;

public class First {
	
	static int countRange(int start, int end, int[] array) {
		//System.out.println("enter countRange");
		int count = 0;
		for(int value: array) {
			if(value >= start && value <= end)
				count++;
		}
		return count;
	}
	
	public static void main(String[] args) {
		//处理输入
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] array = new int[n];
		for(int i = 0; i < n; i++)
			array[i] = in.nextInt();
		//WAY1：创建辅助数组，按照数值与下标对应的思想复制，时间复杂度O(n)，空间复杂度O(n)
		int[] assist = new int[n];
		//Arrays.fill(assist, n);//可以注释掉的原因是题目说的数值范围为1~n，所以不会存在0的情况
		for(int i = 0; i < n; i++) {
			int value = array[i];
			if(assist[value] == value) {
				System.out.println("WAY1:	" + value);
				break;
			}
			else assist[value] = value;
		}
		//WAY2：二分的思想，用一个middle将数据可选范围一分为二；
		//例如统计1~4这几个数字出现的个数，如果出现了5次，那么该范围内必然存在重复数字（鸽巢原理）
		//数组长度n，子函数countRange被调用O(nlogn)次，每次需要O(n)，总的时间复杂度为O(nlogn)，空间复杂度为O(n)
		//时间换空间
		//可能存在一些缺陷，如[1,2]范围内2出现两次，1未出现，但是会计数正常
		int start = 1;
		int end = n - 1;
		while(end >= start) {
			int middle = ((end - start) >> 1) + start;
			//System.out.printf("%d %d %d\n",middle,start,end);
			int count = countRange(start, middle, array);
			if(end == start) {
				System.out.println("WAY2:	" + start);
				break;
			}
			if(count > middle - start + 1)
				end = middle;
			else
				start = middle + 1;
		}
	}
}

输入输出结果：

8
2 3 5 4 3 2 6 7
WAY1:    3
WAY2:    3 

 

本文地址：https://blog.csdn.net/cs18freshman/article/details/110950272