关注
bfprt算法及其相关
找到无序数组中最小的K个数
【题目】
给定一个无序的整型数组arr,找到其中最小的k个数。
【要求】
如果数组arr的长度为N,排序之后自然可以得到最小的k个数,此时时间复杂度为排序的时间复杂度即O(N*logN)。本题要求读者实现时间复杂度O(N*logK)和O(N)的方法。
利用堆:
public int[] getMinKNumsByHeap(int[] arr, int k) {
if (k < 1 || k > arr.length) {
return arr;
}
int[] kHeap = new int[k];
for (int i = 0; i != k; i++) {
heapInsert(kHeap, arr[i], i);
}
for (int i = k; i != arr.length; i++) {
if (arr[i] < kHeap[0]) {
kHeap[0] = arr[i];
heapify(kHeap, 0, k);
}
}
return kHeap;
}
public void heapInsert(int[] arr, int value, int index) {
arr[index] = value;
while (index != 0) {
int parent = (index - 1) / 2;
if (arr[parent] < arr[index]) {
swap(arr, parent, index);
index = parent;
} else {
break;
}
}
}
public void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
while (left < heapSize) {
if (arr[left] > arr[index]) {
largest = left;
}
if (right < heapSize && arr[right] >
arr[largest]) {
largest = right;
}
if (largest != index) {
swap(arr, largest, index);
} else {
break;
}
index = largest;
left = index * 2 + 1;
right = index * 2 + 2;
}
}
public void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
利用bfprt算法:
public int[] getMinKNumsByBFPRT(int[] arr, int k) {
if (k < 1 || k > arr.length) {
return arr;
}
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 int getMinKthByBFPRT(int[] arr, int K) {
int[] copyArr = copyArray(arr);
return select(copyArr, 0, copyArr.length - 1, K - 1);
}
public int[] copyArray(int[] arr) {
int[] res = new int[arr.length];
for (int i = 0; i != res.length; i++) {
res[i] = arr[i];
}
return res;
}
public int select(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 select(arr, begin, pivotRange[0] - 1, i);
} else {
return select(arr, pivotRange[1] + 1, end, i);
}
}
public 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++) {
int beginI = begin + i * 5;
int endI = beginI + 4;
mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
}
return select(mArr, 0, mArr.length - 1, mArr.length / 2);
}
public int[] partition(int[] arr, int begin, int end, int
pivotValue) {
int small = begin - 1;
int cur = begin;
int big = end + 1;
while (cur != big) {
if (arr[cur] < pivotValue) {
swap(arr, ++small, cur++);
} else if (arr[cur] > pivotValue) {
swap(arr, cur, --big);
} else {
cur++;
}
}
int[] range = new int[2];
range[0] = small + 1;
range[1] = big - 1;
return range;
}
public int getMedian(int[] arr, int begin, int end) {
insertionSort(arr, begin, end);
int sum = end + begin;
int mid = (sum / 2) + (sum % 2);
return arr[mid];
}
public void insertionSort(int[] arr, int begin, int end) {
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 void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
今天 09:15
哈尔滨工业大学 电子信息类 点赞 评论 收藏
转发
牛客热帖
- 1... 想来字节技术实习,看我这篇就够了!——保姆级面经大放送1.9W
- 2... 外卖员面试经验1.8W
- 3... 25届第一份实习怎么找?1.7W
- 4... 0实习经验上岸字节,分享一下过程经验1.6W
- 5... 【奖】休息放松or学习提升,五一假期和牛牛一起“充充电”🔋1.5W
- 6... 【0429快问快答】99%牛油的疑惑解答(更新至38个问题1.4W
- 7... 准备去参加自己的婚礼1.2W
- 8... 美团后端日常实习一二面(已oc)9373
- 9... 【💰有奖征集】非技术岗位笔面经邀你来分享!攒人品时间到!8220
- 10... 腾讯后台开发一面4.268162
正在热议
# 牛友的五一计划 #
14614次浏览 318人参与
# 如何看待offer收割机的行为 #
193627次浏览 2979人参与
# 牛客帮帮团来啦!有问必答 #
395531次浏览 7795人参与
# 晒一晒我的offer #
2820762次浏览 49883人参与
# 无实习如何秋招上岸 #
172333次浏览 2714人参与
# 如何一边实习一边秋招 #
201014次浏览 3991人参与
# 春招别灰心,我们一人来一句鼓励 #
21101次浏览 304人参与
# 非技术岗薪资爆料 #
8166次浏览 152人参与
# 硬件人的春招flag #
14522次浏览 199人参与
# 在国企工作的人,躺平了吗? #
72671次浏览 878人参与
# 字节跳动工作体验 #
52823次浏览 1502人参与
# 聊聊这家公司值得去吗 #
62596次浏览 1203人参与
# 女生做医疗销售有前景吗 #
3844次浏览 48人参与
# 第一次面试 #
16849次浏览 255人参与
# 来聊聊机械薪资天花板是哪家 #
22470次浏览 178人参与
# 机械人,你的秋招第一份简历被谁挂了 #
26939次浏览 491人参与
# 你更愿意参加线上面试还是线下面试? #
6871次浏览 94人参与
# 华为求职进展汇总 #
441420次浏览 4432人参与
# 机械制造2024笔面经 #
278117次浏览 4661人参与
# 如何KTV领导 #
7478次浏览 72人参与