首页 技术 正文
技术 2022年11月23日
0 收藏 470 点赞 2,550 浏览 2560 个字

(referrence: GeeksforGeeks, Kth Largest Element in Array)

This is a common algorithm problem appearing in interviews.

There are four basic solutions.

Solution 1 — Sort First

A Simple Solution is to sort the given array using a O(n log n) sorting algorithm like Merge Sort,Heap Sort, etc and return the element at index k-1 in the sorted array. Time Complexity of this solution is O(n log n).

Java Arrays.sort()

 public class Solution{
public int findKthSmallest(int[] nums, int k) {
Arrays.sort(nums);
return nums[k];
}
}

Solution 2 — Construct Min Heap

A simple optomization is to create a Min Heap of the given n elements and call extractMin() k times.

To build a heap, time complexity is O(n). So total time complexity is O(n + k log n).

Java Priority Queue

Using PriorityQueue(Collection<? extends E> c), we can construct a heap from array or other object in linear time.

By defaule, it will create a min-heap.

Example

 public int generateHeap(int[] nums) {
int length = nums.length;
Integer[] newArray = new Integer[length];
for (int i = 0; i < length; i++)
newArray[i] = (Integer)nums[i];
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Arrays.asList(newArray));
}

Comparator example

Comparator cmp = Colletions.reverseOrder();

Solution 3 — Use Max Heap

1. Build a max-heap of size k. Put nums[0] to nums[k – 1] to heap.

2. For each element after nums[k – 1], compare it with root of heap.

  a. If current >= root, move on.

  b. If current <  root, remove root, put current into heap.

3. Return root.

Time complexity is O((n – k) log k).

(Java: PriorityQueue)

Kth Smallest Element in Unsorted Array

(codes)

 public class Solution {
public int findKthSmallest(int[] nums, int k) {
// Construct a max heap of size k
int length = nums.length;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, Collections.reverseOrder());
for (int i = 0; i < k; i++)
pq.add(nums[i]);
for (int i = k; i < length; i++) {
int current = nums[i];
int root = pq.peek();
if (current < root) {
// Remove head
pq.poll();
// Add new node
pq.add(current);
}
}
return pq.peek();
}
}

Solution 4 — Quick Select

public class Solution {
private void swap(int[] nums, int index1, int index2) {
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
} // Pick last element as pivot
// Place all smaller elements before pivot
// Place all bigger elements after pivot
private int partition(int[] nums, int start, int end) {
int pivot = nums[end];
int currentSmaller = start - 1;
for (int i = start; i < end; i++) {
// If current element <= pivot, put it to right position
if (nums[i] <= pivot) {
currentSmaller++;
swap(nums, i, currentSmaller);
}
}
// Put pivot to right position
currentSmaller++;
swap(nums, end, currentSmaller);
return currentSmaller;
} public int quickSelect(int[] nums, int start, int end, int k) {
int pos = partition(nums, start, end)
if (pos == k - 1)
return nums[pos];
if (pos < k - 1)
return quickSelect(nums, pos + 1, end, k - (pos - start + 1));
else
return quickSelect(nums, start, pos - 1, k);
}
}

The worst case time complexity of this method is O(n2), but it works in O(n) on average.

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141256.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:4,994
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,472
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,281
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,282
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,840
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,072
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站