1+ /**
2+ * 1、对原数组进行排序
3+ * 2、打乱了原数组，不符合要求
4+ *
5+ */
6+ public class FindDuplicate {
7+ public int findDuplicate (int [] nums ) {
8+ int result = 0 ;
9+ int low = 0 , high = nums .length ;
10+ quickSort (nums , low , high - 1 );
11+ for (int i = 1 ; i < high ; i ++){
12+ if (nums [i - 1 ] == nums [i ]){
13+ result = nums [i ];
14+ break ;
15+ }
16+ }
17+ return result ;
18+ }
19+
20+ public void quickSort (int [] arr , int low , int high ) {
21+ if (low >= high ){
22+ return ;
23+ }
24+ int mid = partion (arr , low , high );
25+ quickSort (arr , low , mid - 1 );
26+ quickSort (arr , mid + 1 , high );
27+ }
28+
29+ private int partion (int [] arr , int low , int high ) {
30+ int pivot = arr [low ];
31+ int i = low , j = high + 1 ;
32+
33+ while (true ) {
34+ while (less (arr [++i ], pivot )) if (i == high ) break ;
35+ while (less (pivot , arr [--j ])) if (j == low ) break ;
36+ // check if pointers cross
37+ if (i >= j ) break ;
38+ exch (arr , i , j );
39+ }
40+ // put partitioning item v at a[j]
41+ exch (arr , low , j );
42+
43+ // now, a[low .. j-1] <= a[j] <= a[j+1 .. high]
44+ return j ;
45+ }
46+
47+ private boolean less (int v , int w ) {
48+ return v < w ? true : false ;
49+ }
50+
51+ // exchange a[i] and a[j]
52+ private void exch (int [] a , int i , int j ) {
53+ int swap = a [i ];
54+ a [i ] = a [j ];
55+ a [j ] = swap ;
56+ }
57+
58+ }
0 commit comments