(referrence: , )

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).

1 public class Solution{2     public int findKthSmallest(int[] nums, int k) {3         Arrays.sort(nums);4         return nums[k];5     }6 }

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).

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

1 public int generateHeap(int[] nums) {2         int length = nums.length;3         Integer[] newArray = new Integer[length];4         for (int i = 0; i < length; i++)5             newArray[i] = (Integer)nums[i];6         PriorityQueue
     
       pq = new PriorityQueue
      
       (Arrays.asList(newArray));7     }
      
     

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)

(codes)

1 public class Solution { 2     public int findKthSmallest(int[] nums, int k) { 3         // Construct a max heap of size k 4         int length = nums.length; 5         PriorityQueue
     
       pq = new PriorityQueue
      
       (k, Collections.reverseOrder()); 6         for (int i = 0; i < k; i++) 7             pq.add(nums[i]); 8         for (int i = k; i < length; i++) { 9             int current = nums[i];10             int root = pq.peek();11             if (current < root) {12                 // Remove head13                 pq.poll();14                 // Add new node15                 pq.add(current);16             }17         }18         return pq.peek();19     }20 }
      
     

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(n²), but it works in O(n) on average.