# Kth Smallest Element in Unsorted Array 2022年11月23日
0 收藏 470 点赞 2,658 浏览 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 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) (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. 微信扫一扫 支付宝扫一扫 python开发_常用的python模块及安装方法 Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes… zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…  Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显… Struts的使用 