题目1：求无序数组第k小的数
可采用改写快排的方式，也可采用bfprt算法
// 算法1：使用大根堆，时间复杂度O(n*logk)public static int findKthMinNum1(int[] arr, int k) {PriorityQueue<Integer> maxHeap = new PriorityQueue<>((i1, i2) -> i2 - i1);for (int i = 0; i < k; i++) {maxHeap.offer(arr[i]);}for (int i = k; i < arr.length; i++) {if (arr[i] < maxHeap.peek()) {maxHeap.poll();maxHeap.offer(arr[i]);}}return maxHeap.peek();}
public static int findKthMinNum2(int[] arr, int k) {return process(copyArr(arr), 0, arr.length - 1, k - 1);}private static int[] copyArr(int[] arr) {return Arrays.copyOf(arr, arr.length);}private static int process(int[] arr, int l, int r, int index) {if (l == r) {return arr[l];}int pivot = arr[l + (int) (Math.random() * (r - l + 1))];int[] range = partition(arr, l, r, pivot);if (index >= range[0] && index <= range[1]) {return arr[index];} else if (index < range[0]) {return process(arr, l, range[0] - 1, index);} else {return process(arr, range[1] + 1, r, index);}}public static int[] partition(int[] arr, int l, int r, int pivot) {int less = l - 1;int more = r + 1;int cur = l;while (cur < more) {if (arr[cur] < pivot) {swap(arr, ++less, cur++);} else if (arr[cur] > pivot) {swap(arr, cur, --more);} else {cur++;}}return new int[]{less + 1, more - 1};}private static void swap(int[] arr, int i1, int i2) {int tmp = arr[i1];arr[i1] = arr[i2];arr[i2] = tmp;}
public static int findKthMinNum3(int[] arr, int k) {return bfprt(copyArr(arr), 0, arr.length - 1, k - 1);}public static int bfprt(int[] arr, int l, int r, int index) {if (l == r) {return arr[l];}// L...R 每五个数一组// 每一个小组内部排好序// 小组的中位数组成新数组// 这个新数组的中位数返回int pivot = medianOfMedian(arr, l, r);int[] range = partition(arr, l, r, pivot);if (index >= range[0] && index <= range[1]) {return arr[index];} else if (index < range[0]) {return bfprt(arr, l, range[0] - 1, index);} else {return bfprt(arr, range[1] + 1, r, index);}}/*** 以5位元素为一组，排序，获取每组的中点，组成新的一组，返回新组的中点*/public static int medianOfMedian(int[] arr, int l, int r) {int size = r - l + 1;int offset = size % 5 == 0 ? 0 : 1;int mSzie = size / 5 + offset;int[] mArr = new int[mSzie];for (int team = 0; team < mSzie; team++) {int teamFirst = l + team * 5;mArr[team] = getMedian(arr, teamFirst, Math.min(r, teamFirst + 4));}return bfprt(mArr, 0, mSzie - 1, mArr.length >> 1);}public static int getMedian(int[] arr, int l, int r) {insertionSort(arr, l, r);return arr[l + ((r - l) >> 1)];}public static void insertionSort(int[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {for (int j = i - 1; j >= l && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);}}}public static int[] partition(int[] arr, int l, int r, int pivot) {int less = l - 1;int more = r + 1;int cur = l;while (cur < more) {if (arr[cur] < pivot) {swap(arr, ++less, cur++);} else if (arr[cur] > pivot) {swap(arr, cur, --more);} else {cur++;}}return new int[]{less + 1, more - 1};}private static void swap(int[] arr, int i1, int i2) {int tmp = arr[i1];arr[i1] = arr[i2];arr[i2] = tmp;}
题目2：返回topk个最大的数
给定一个无序数组arr中，长度为N，给定一个正数k，返回topk个最大的数
//排序+收集 时间复杂父 O(n*logN)
public static int[] getTopK1(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return new int[0];
}
int n = arr.length;
k = Math.min(n, k);
Arrays.sort(arr);
int[] res = new int[k];
for (int i = n - 1, j = 0; j < k; i--, j++) {
res[j] = arr[i];
}
return res;
}
// 使用了堆结构，时间复杂度O(n+K*logn)
public static int[] getTopK2(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return new int[0];
}
int n = arr.length;
for (int i = n - 1; i >= 0; i--) {
heapify(arr, i, n);
}
int heapSize = n;
int count = 0;
while (heapSize > 0 && count < k) {
swap(arr, 0, --heapSize);
heapify(arr, 0, heapSize);
count++;
}
k = Math.min(n, k);
int[] res = new int[k];
for (int i = n - 1, j = 0; j < k; i--, j++) {
res[j] = arr[i];
}
return res;
}
private static void heapify(int[] arr, int i, int size) {
int left = 2 * i + 1;
while (left < size) {
int bigIndex = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
bigIndex = arr[i] >= arr[bigIndex] ? i : bigIndex;
if (bigIndex == i) {
break;
}
swap(arr, i, bigIndex);
i = bigIndex;
left = 2 * i + 1;
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// 时间复杂度O(N+k*logk)
public static int[] getTopK3(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return new int[0];
}
int n = arr.length;
k = Math.min(k, n);
int num = minK(arr, n - k);
int[] res = new int[k];
int index = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > num) {
res[index++] = arr[i];
}
}
for (; index < k; index++) {
res[index] = num;
}
Arrays.sort(res);
for (int l = 0, r = k - 1; l < r; l++, r--) {
swap(res, l, r);
}
return res;
}
private static int minK(int[] arr, int i) {
return bfprt(Arrays.copyOf(arr, arr.length), i - 1);
}
private static int bfprt(int[] arr, int index) {
int l = 0;
int r = arr.length - 1;
while (l < r) {
int pivot = medianOfMedian(arr, l, r);
int[] range = partition(arr, l, r, pivot);
if (index >= range[0] && index <= range[1]) {
return arr[index];
} else if (index < range[0]) {
r = range[0] - 1;
} else {
l = range[1] + 1;
}
}
return arr[l];
}
private static int[] partition(int[] arr, int l, int r, int pivot) {
int less = l - 1;
int more = r + 1;
int cur = l;
while (cur < more) {
if (arr[cur] < pivot) {
swap(arr, ++less, cur++);
} else if (arr[cur] > pivot) {
swap(arr, cur, --more);
} else {
cur++;
}
}
return new int[]{less + 1, more - 1};
}
private static int medianOfMedian(int[] arr, int l, int r) {
int size = r - l + 1;
int offset = size % 5 == 0 ? 0 : 1;
int mSzie = size / 5 + offset;
int[] mArr = new int[mSzie];
for (int team = 0; team < mSzie; team++) {
int teamFirst = l + team * 5;
mArr[team] = median(arr, teamFirst, Math.min(r, teamFirst + 4));
}
return mArr[mSzie >> 1];
}
private static int median(int[] arr, int l, int r) {
insertSort(arr, l, r);
return arr[l + ((r - l) >> 1)];
}
private static void insertSort(int[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
for (int j = i - 1; j >= l && arr[j + 1] < arr[j]; j--) {
swap(arr, j, j + 1);
}
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
若有收获，就点个赞吧
0 人点赞
