|
1 | 1 | classSolution { |
| 2 | + |
| 3 | +enumDirection {LEFT,RIGHT}; |
| 4 | + |
2 | 5 | publicintfindSpecialInteger(int[]arr) { |
3 | 6 | intn =arr.length; |
4 | | -intoneFourthNum =arr[n /4]; |
5 | | -inthalfNum =arr[n /2]; |
6 | | -intthreeFourthNum =arr[3 *n /4]; |
7 | | -if(Math.max(n/4,binarySearchRight(arr,0,n -1,oneFourthNum)) - |
8 | | -Math.min(n/4,binarySearchLeft(arr,0,n -1,oneFourthNum)) >=arr.length /4) { |
9 | | -returnoneFourthNum; |
10 | | - } |
11 | | -if(Math.max(n/2,binarySearchRight(arr,0,n -1,halfNum)) - |
12 | | -Math.min(n/2,binarySearchLeft(arr,0,n -1,halfNum)) >=arr.length /4) { |
13 | | -returnhalfNum; |
14 | | - } |
15 | | -if(Math.max((3 *n)/4,binarySearchRight(arr,0,n -1,threeFourthNum)) - |
16 | | -Math.min((3 *n)/4,binarySearchLeft(arr,0,n -1,threeFourthNum)) >=arr.length /4) { |
17 | | -returnthreeFourthNum; |
18 | | - } |
19 | | -return -1; |
20 | | - } |
21 | | - |
22 | | -privateintbinarySearchLeft(int[]arr,intstart,intend,intnum) { |
23 | | -intminIdx =Integer.MAX_VALUE; |
24 | | -while (start <end) { |
25 | | -intmid = (start +end) /2; |
26 | | -if (arr[mid] ==num) { |
27 | | -minIdx =Math.min(mid,minIdx); |
28 | | -end =mid -1; |
29 | | - } |
30 | | -elseif (arr[mid] <num) { |
31 | | -start =mid +1; |
32 | | - } |
33 | | -else { |
34 | | -end =mid -1; |
| 7 | +if (n ==1) { |
| 8 | +returnarr[0]; |
| 9 | + } |
| 10 | +List<Integer>list =Arrays.asList(arr[n /4],arr[n /2],arr[3 *n /4]); |
| 11 | +for (intnum :list) { |
| 12 | +intfirstPosition =getPosition(arr,num,Direction.LEFT); |
| 13 | +intlastPosition =getPosition(arr,num,Direction.RIGHT); |
| 14 | +if (lastPosition -firstPosition +1 >n /4) { |
| 15 | +returnnum; |
35 | 16 | } |
36 | 17 | } |
37 | | -returnminIdx; |
| 18 | +return-1; |
38 | 19 | } |
39 | 20 |
|
40 | | -privateintbinarySearchRight(int[]arr,intstart,intend,intnum) { |
41 | | -intmaxIdx =Integer.MIN_VALUE; |
42 | | -while (start <end) { |
43 | | -intmid = (start +end) /2; |
44 | | -if (arr[mid] ==num) { |
45 | | -maxIdx =Math.max(mid,maxIdx); |
46 | | -start =mid +1; |
47 | | - } |
48 | | -elseif (arr[mid] <num) { |
49 | | -start =mid +1; |
50 | | - } |
51 | | -else { |
52 | | -end =mid -1; |
| 21 | +privateintgetPosition(int[]nums,intnum,Directiondirection) { |
| 22 | +intleft =0; |
| 23 | +intright =nums.length -1; |
| 24 | +intidx = -1; |
| 25 | +while (left <=right) { |
| 26 | +intmid = (left +right) /2; |
| 27 | +if (nums[mid] ==num) { |
| 28 | +idx =mid; |
| 29 | +if (direction ==Direction.LEFT) { |
| 30 | +right =mid -1; |
| 31 | + }else { |
| 32 | +left =mid +1; |
| 33 | + } |
| 34 | + }elseif (nums[mid] >num) { |
| 35 | +right =mid -1; |
| 36 | + }else { |
| 37 | +left =mid +1; |
53 | 38 | } |
54 | 39 | } |
55 | | -returnmaxIdx; |
| 40 | +returnidx; |
56 | 41 | } |
57 | 42 | } |