forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBFPRT.java
More file actions
129 lines (117 loc) · 3.59 KB
/
BFPRT.java
File metadata and controls
129 lines (117 loc) · 3.59 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package Others;
import java.util.Arrays;
/**
* BFPRT algorithm.
*/
public class BFPRT {
public static int[] getMinKNumsByBFPRT(int[] arr, int k) {
if (k < 1 || k > arr.length) {
return null;
}
int minKth = getMinKthByBFPRT(arr, k);
int[] res = new int[k];
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < minKth) {
res[index++] = arr[i];
}
}
for (; index != res.length; index++) {
res[index] = minKth;
}
return res;
}
public static int getMinKthByBFPRT(int[] arr, int k) {
int[] copyArr = copyArray(arr);
return bfprt(copyArr, 0, copyArr.length - 1, k - 1);
}
public static int[] copyArray(int[]arr) {
int[] copyArr = new int[arr.length];
for(int i = 0; i < arr.length; i++) {
copyArr[i] = arr[i];
}
return copyArr;
}
public static int bfprt(int[] arr, int begin, int end, int i) {
if (begin == end) {
return arr[begin];
}
int pivot = medianOfMedians(arr, begin, end);
int[] pivotRange = partition(arr, begin, end, pivot);
if (i >= pivotRange[0] && i <= pivotRange[1]) {
return arr[i];
} else if (i < pivotRange[0]) {
return bfprt(arr, begin, pivotRange[0] - 1, i);
} else {
return bfprt(arr, pivotRange[1] + 1, end, i);
}
}
/**
* wikipedia: https://en.wikipedia.org/wiki/Median_of_medians .
* @param arr an array.
* @param begin begin num.
* @param end end num.
* @return median of medians.
*/
public static int medianOfMedians(int[] arr, int begin, int end) {
int num = end - begin + 1;
int offset = num % 5 == 0 ? 0 : 1;
int[] mArr = new int[num / 5 + offset];
for (int i = 0;i < mArr.length;i++) {
mArr[i] = getMedian(arr, begin + i * 5, Math.min(end, begin + i * 5 + 4));
}
return bfprt(mArr, 0, mArr.length - 1, mArr.length / 2);
}
public static void swap(int[]arr, int i, int j) {
int swap = arr[i];
arr[i] = arr[j];
arr[j] = swap;
}
public static int[] partition(int[] arr,int begin,int end,int num)
{
int small=begin-1;
int cur=begin;
int big=end+1;
while(cur!=big)
{
if (arr[cur]<num)
{
swap(arr,++small,cur++);
}else if (arr[cur]>num)
{
swap(arr,--big,cur);
} else {
cur++;
}
}
int[] pivotRange=new int[2];
pivotRange[0]=small+1;
pivotRange[1]=big-1;
return pivotRange;
}
public static int getMedian(int[] arr, int begin, int end) {
insertionSort(arr, begin, end);
int sum = begin + end;
int mid = sum / 2 + (sum % 2);
return arr[mid];
}
public static void insertionSort(int[] arr, int begin, int end) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = begin + 1;i != end + 1;i++) {
for (int j = i;j != begin;j--) {
if (arr[j - 1] > arr[j]) {
swap(arr, j - 1, j);
} else {
break;
}
}
}
}
public static void main(String[] args) {
int[] arr = { 11, 9, 1, 3, 9, 2, 2, 5, 6, 5, 3, 5, 9, 7, 2, 5, 5, 1, 9 };
int[] minK = getMinKNumsByBFPRT(arr,5);
System.out.println(Arrays.toString(minK));
}
}