Problem 1 K smallest In Unsorted Array

Method 1: Sorting

• (体会下考点不再这里)==》 面试里提一个即可，不要浪费时间

High Level:

• 把数组从小到大排列

• 前k个元素就是最小的k个元素

TC& SC

• O(nlogn), O(sort)

public class Solution {
    public int[] kSmallest(int[] array, int k) {
        Arrays.sort(array);
        int[] result = new int[k];
        for (int i = 0; i< k; i++) {
            result[i] = array[i];
        }
        return result;
    }
}

Method 1b: 用heap sort，不用API

• 我要用Heap Sort,不用API

  • step 1: 开个heap

  • step 2: 把所有的元素都放在heap里,再拿出来一遍

• 这个方法不是heap sort，heap sort的最大的优势

  • 不仅是可以和mergeSort一样能达到nlogn的时间

  • 而且人家是space O(1)

class solution {
    public int[] kSmallest(int[] array, int k) {
        heapify(array); // 把你给我的array变成一个heap 
            // 你heap完没有按顺序啊，所以我每次只能拿出来在最前面的那个
            // 所以后面每一步，我需要从第0个，一个个percolateDown，确保从第0个到第k-1个都是排好序的
        for (int i = 0 ; i < array.length; i++) {
            swap(array, 0, array.length - 1 - i);//这一步意味着倒数第i个元素已经完成了排序
            // 接下来调整0到array.length - 1 - i
            percolateDown(array, 0, array.length - 1 - i);
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = array[i];
        }
    }
    private void heapify(int[] arr) {
        for (int i = arr.length/ 2 - i ; i >= 0; i--) {
            percolateDown(arr, i, arr.length);
        }
    }
    private void swap (int[] arr, int i , int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private void percolateDown(int[] array, int index, int size) {
        while ( 2* index + 2 <= size) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int candidateChild = leftChild;
            if (rightChild <= size && array[rightChild] > array[leftChild]) {
                candidateChild = rightChild;
            }
            if (array[index] > array[candidateChild]){
                swap(array, index, candidateChild);
            } else{
                break;
            }
            index = candidateChild;
        }
    }
}

TC : O(n) + O(klogn) + O(k) ==> O(nlogn)

SC: O(1)

Method 2 MinHeap（两种）

方法论：当题目求的topK和Kth和你的heap比较的优先级一致的时候，全放进去，poll K次

• TC: O(nlogn)

• SC: O(n)

public int[] kSmallest(int[] array, int k) {
    PriorityQueue<Integer> minHeap = new ArrayQueue<>();
    for (int num: array) {
        minHeap.offer(num);
    }
    int[] result = new int[Math.min(minHeap.size()),k];
    for(int i = 0; i < result.length; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

• 自己实现heapify且直接poll up前k个

• 和前面不一样，前面那个是sort好，再解决，这个是每次都poll直到第k次，所以时间会变成O(klog n)

public class Solution {
  public int[] kSmallest(int[] array, int k) {
    // Write your solution here

    // sanity check
    if (array == null || array.length == 0 || k <=0) {
      return new int[]{};
    }

    // build the minheap
    heapify(array, 0, array.length - 1);
    
    // poll k smallest element out
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
      result[i] = array[0];
      swap(array, 0, array.length - i - 1);
      percolateDown(array, 0, array.length - i - 1);// 下一次少了一个
    }
    return result;
  }
  private void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
  }
  
  private void heapify(int[] array, int left, int right) {
    int size = right - left + 1;
    for (int i = size /2 - 1; i >= 0; i--) {
      percolateDown(array, i, size);
    }
  }
  private void percolateDown(int[] array, int index, int size) {
    while (index <= size / 2 -  1) {
      int leftIndex = index * 2 + 1;
      int rightIndex = index * 2 + 2;
      int candIndex = leftIndex;
      if (rightIndex < size && array[rightIndex] < array[leftIndex]) {
        candIndex = rightIndex;
      }
      if (array[candIndex] < array[index]) {
        swap(array, candIndex, index);
      } else {
        break;
      }
      index = candIndex;
    }
  }
}

TC: O(n + k logn)

SC: O(1)

Method 3: MaxHeap（两种）

方法论：当题目求的topK和Kth和你的Heap比较的优先级不一样

• 你的heap里装的是：到目前为止topK candidate

  • 手头先攥k个，这些是候选人

  • 然后再撸那些没看过的元素，如果你看到更优先，我们得淘汰手头最不优先的

public class KSmallest{
    
    public int[] kSmallest(int[] array, int k) {
        // sanity check
        if (array.length == 0 || k == 0) {
            return new int[]{0};
        }
        // build the pq
        //PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k , new Comparator<Integer>() {
            //@Override
            //public int compare(Integer o1, Integer o2) {
                //if (o1.equals(o2) {
                    //return 0;
                //}
                //return o1 > o2 ? -1: 1;
            //}
        //})        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collection.reverseOrder());
        
        // offer pq in and poll when pq.size() > k
        //for (int i = 0; i < array.length; i++) {
            //if (i < k) {
               // maxHeap.offer(array[i]);
            //}
            //else if (array[i] < maxHeap.peek()) {
                //maxHeap.poll();
                //maxHeap.offer(array[i]);
            //}
        //}    
        for (int i = 0; i < array.length; i++) {
            maxHeap.offer(array[i]);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }  
        
        // post processing return all result
        
        int[] result = new int[k];
        for (int i = k -1; i >= 0; i--) {
            result[i] = maxHeap.poll();
        }
        return result;
    }
}

这个方法能用heapify优化么？

• 这个方法是把前k个元素放到heap里，是k size heap

• heapify应该是O(k)，不应该是O(n)---> 我们只应该heapify前k个元素)

• ---> 本质上实现一个带range的heapify

public int[] kSmallest(int[] array, int k) {
    heapify(array, 0 , k -1);
    // step 1: build the similuated heap in [0, k- 1]
    
    // step 2: try to find the good candidate if array[new] < array[0]
        // swap, percolatedDown
    for (int i = k; i < array.length; i++) {
        if (array[i] < array[0]) { // new candidate is better the worst one
            swap(array, 0, i);
            percolateDown(array, 0, i);
        }
    }
    // step 3:
        // get the result out from small to large 
        // 你应该每次都是从0th拿出来，但是还是需要percolateDown
    int[] result = new int[k];
    for (i = k - 1; i >= 0; i--) { //注意第一个已经先拿出来，所以一共是k个
        result[i] = array[0];
        swap(array, 0, i);
        percolateDown(array, 0, i);
    }
    return result;
}

private void swap(int[] array, int i, int j) {
    int temp = int[i];
    int[i] = int[j];
    int[j] = temp; 
}
private void percolateDown(int[] array, int index, int size) {
    while (index * 2 + 2 < size) {
        int leftChild = index * 2 + 1;
        int rightChild = index * 2 +2;
        int candidate = leftChild;
        if (rightChild < size && array[rightChild] > array[leftChild]) {
            candidate = rightChild;
        }
        if (array[candiate] > array[index]) {
            swap(array, candidate, index);
        }
        else {
            break;
        }
        index = candidate;
    }
}
private void heapify(int[] array, int left, int right) {
    int size = right - left + 1;
    for (int i = size / 2 - 1; i >= 0; i--) { [left, left + size/ 2 - 1]
        percolateDown(arr, i, size);
    }
}

TC: O(k + (n - k) log k)

SC: O(1)

• 拓展：percolate and heapify只针对left = 0的代码

  • 如果你想要拓展，必须保证left对应第一个元素，采用offset或者[left, right]

• This one also works for online algorithm

• 体现出实时性，如果不需要读完完整的input就可以实时的知道，到目前为止的结果，这就是online算法。不然我们就称之为offline算法