1+ package com .pancm .arithmetic .jzoffer ;
2+
3+ /**
4+ * https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
5+ *
6+ * @description:
7+ * 3.数组中的重复数字
8+ * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。
9+ * 数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。
10+ * 请找出数组中任意一个重复的数字。
11+ *
12+ * @author: Zhoust
13+ * @date: 2019/04/28 10:58
14+ * @version: V1.0
15+ */
16+ public class DuplicateNumberInArray {
17+
18+ /**
19+ * 一种简单的实现思路，借助外部数组保存 numbers 中每个值的出现次数，即 numbers 中的值作为数组 array 的下标。
20+ * 题目中说了长度为 n 的数组中每个值都在 0 到 n-1 范围内，因此遍历数组 numbers 存入对应的 array 不会出现数组下标越界的问题
21+ * @param numbers
22+ * @param length numbers 数组的长度
23+ * @param duplication (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
24+ * 这里要特别注意~返回任意重复的一个，赋值duplication[0]
25+ * @return true if the input is valid, and there are some duplications in the array number, otherwise false
26+ */
27+ public boolean duplicate (int [] numbers , int length , int [] duplication ) {
28+ if (numbers == null ) {
29+ return false ;
30+ }
31+ boolean result = false ;
32+ int [] array = new int [length ];
33+ for (int i = 0 ; i < length ; i ++) {
34+ if (++array [numbers [i ]] > 1 && !result ) {
35+ result = true ;
36+ duplication [0 ] = numbers [i ];
37+ }
38+ }
39+ return result ;
40+ }
41+
42+ /**
43+ * 先排序，然后找到排序后数组中第一个重复的数字（主要就是练习一下快排）
44+ * @param numbers
45+ * @param length
46+ * @param duplication
47+ * @return
48+ */
49+ public boolean sortThenFindFirstDuplicateNumber (int [] numbers , int length , int [] duplication ) {
50+ if (numbers == null ) {
51+ return false ;
52+ }
53+ quickSort (numbers , 0 , length -1 );
54+ int temp = numbers [0 ];
55+ boolean result = false ;
56+
57+ for (int i = 1 ; i < length ; i ++) {
58+ if (numbers [i ] == temp ) {
59+ result = true ;
60+ duplication [0 ] = temp ;
61+ break ;
62+ }
63+ temp = numbers [i ];
64+ }
65+ return result ;
66+ }
67+
68+ /**
69+ * 将值为 i 的元素调整到下标为 i 的位置，如果该位置上的数已经等于 i 了，就说明 i 已经重复了
70+ * @param numbers
71+ * @param length
72+ * @param duplication
73+ * @return
74+ */
75+ public static boolean jz (int [] numbers , int length , int [] duplication ) {
76+ for (int i = 0 ; i < length ; i ++) {
77+ //第 i 个位置上的数 numbers[i] 若不与下标 i 相等，就把 numbers[i] 放到下标为 numbers[i] 的位置
78+ while (numbers [i ] != i ) {
79+ //在交换位置之前还要检查 numbers[i] 位置上的数字是否已经是 numbers[i]，如果是就已经找到了重复的数字
80+ if (numbers [numbers [i ]] == numbers [i ]) {
81+ duplication [0 ] = numbers [i ];
82+ //注意这里不是 break
83+ return true ;
84+ }
85+
86+ //交换下标为 i、numbers[i] 两个位置上的数字（保证下标为 numbers[i] 的位置，放置的数字是 numbers[i]）
87+ swap (numbers , i , numbers [i ]);
88+ }
89+ }
90+ return false ;
91+ }
92+
93+ /**
94+ * 交换下标为 i、j 的两个数
95+ * @param numbers
96+ * @param i
97+ * @param j
98+ */
99+ public static void swap (int [] numbers , int i , int j ) {
100+ int swap = numbers [i ];
101+ numbers [i ] = numbers [j ];
102+ numbers [j ] = swap ;
103+ }
104+
105+ /**
106+ * 快排
107+ * @param array
108+ * @param length
109+ */
110+ @ SuppressWarnings ("all" )
111+ public static void quickSort (int [] array , int low , int high ) {
112+ //这里必须首先限制 low<high，否则会出现 ArrayIndexOutOfBoundsException，当
113+ if (low < high ) {
114+ int temp = array [low ];
115+ int l = low , h = high ;
116+ while (l != h ) {
117+ while (array [h ] > temp && h > l ) {
118+ h --;
119+ }
120+ array [l ] = array [h ];
121+ while (array [l ] <= temp && l < h ) {
122+ l ++;
123+ }
124+ array [h ] = array [l ];
125+ }
126+ array [l ] = temp ;
127+ quickSort (array , low , h -1 );
128+ quickSort (array , l +1 , high );
129+ }
130+ }
131+
132+ public static void main (String [] args ) {
133+ int [] result = new int [1 ];
134+ jz (new int []{2 ,4 ,2 ,1 ,4 }, 5 , result );
135+ System .out .println (result [0 ]);
136+ // int[] d = new int[1];
137+ // jz(new int[]{2,1,3,0,4}, 5, d);
138+ // int[] array = new int[]{1,4,4,4,12,78,8,45,67,39,20,90,65,34,34,6,7,88,9,1,-3,-88,-2};
139+ int [] array = new int []{2 ,4 ,3 ,1 ,4 };
140+ quickSort (array , 0 , array .length -1 );
141+ for (int i = 0 ; i < array .length ; i ++) {
142+ System .out .println (array [i ]);
143+ }
144+
145+ }
146+
147+ }
0 commit comments