Kth Largest Element in an Array

排序然后取nums[n-k]
- O(N lg N) running time + O(1) memory
PriorityQueue **只要见到集合求min/max就要想到用heap
- PriorityQueue默认是最小堆的，通过维护size=k来保证每次进来的都是更大的数，最终第k大的数是这个堆里的min. 注意在这种求第kth大，前k大个元素的要求时，用的是最小堆。反之，求最小的时候，用最大堆。这样就可以保证这个堆里永远只有k个树，只有在堆超过k个数或者比堆顶的数大来决定是否要更新堆
- O(N lg K) running time + O(K) memory
```
public int findKthLargest(int[] nums, int k) {

final PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int val : nums) {
   pq.offer(val);

   if(pq.size() > k) {
       pq.poll();
   }
}
return pq.peek();
}
```
利用快速排序中的选择算法 Todo: 做一下http://www.jiuzhang.com/solution/kth-smallest-numbers-in-unsorted-array/
- O(N) best case and O(N^2) worst case
- 快速排序的理解
  - storeIndex 这里表达的是最终partition后，pivot所在的位置，在partition的过程中，storeIndex从最左端出发，不断与小于pivot的值的坐标交换。于是storeIndex就成为了左侧小于pivot的数的下一个树，即pivot最后需要换到的位置
  - 通过partition，我们可以把数组分成比pivot大和小两部分。而在这道题中，我们只需要让左侧部分的个数或者右侧部分个数满足题目条件即可

  //iterative
  private static int iterative(int[] array, int left, int right, int n) {
          if(left == right) {
              return array[left];
          }

          for(;;) {
              int pivotIndex = randomPivot(left, right);
              pivotIndex = partition(array, left, right, pivotIndex);

              if(n == pivotIndex) {
                  return array[n];
              } else if(n < pivotIndex) {
                  right = pivotIndex - 1;
              } else {
                  left = pivotIndex + 1;
              }
          }
    }


  // recursive
  private static int recursive(int[] array, int left, int right, int n) {
        if (left == right) { // If the list contains only one element,
            return array[left]; // return that element
        }

        // select a pivotIndex between left and right
        int pivotIndex = randomPivot(left, right); 
        pivotIndex = partition(array, left, right, pivotIndex);
        // The pivot is in its final sorted position
        if (n == pivotIndex) {
            return array[n];
        } else if (n < pivotIndex) {
            return recursive(array, left, pivotIndex - 1, n);
        } else {
            return recursive(array, pivotIndex + 1, right, n);
        }
    }

  private static int partition(int[] array, int left, int right, int pivotIndex) {
        int pivotValue = array[pivotIndex];
        swap(array, pivotIndex, right); // move pivot to end
        int storeIndex = left;
        for(int i = left; i < right; i++) {
            if(array[i] < pivotValue) {
                swap(array, storeIndex, i);
                storeIndex++;
            }
        }
        swap(array, right, storeIndex); // Move pivot to its final place
        return storeIndex;
    }

 public int kthLargestElement(int k, int[] nums) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int start, int end, int k) {
        int left = start, right = end;
        int pivot = nums[(start + end) / 2];

        while (left <= right) {
            while (left <= right && nums[left] > pivot) {
                left++;
            }
            while (left <= right && nums[right] < pivot) {
                right--;
            }

            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;

                left++;
                right--;
            }
        }

        if (start + k - 1 <= right) {
            return quickSelect(nums, start, right, k);
        }

        if (start + k - 1 >= left) {
            return quickSelect(nums, left, end, k - (left - start));
        }

        return nums[right + 1];
    }

Kth Smallest Element in a BST

inorder traverse

注意到这里只关注第k小的，所以不需要保存到一个数组，直接通过一个计数器来确定什么时候退出即可

//recursive
private static int number = 0;
private static int count = 0;

public int kthSmallest(TreeNode root, int k) {
    count = k;
    helper(root);
    return number;
}

public void helper(TreeNode n) {
    if (n.left != null) helper(n.left);
    count--;
    if (count == 0) {
        number = n.val;
        return;
    }
    if (n.right != null) helper(n.right);
} 
//iterative
public ArrayList<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curt = root;

while (curt != null || !stack.empty()) {
    while (curt != null) {
        stack.add(curt);
        curt = curt.left;
    }
    //no left sub tree, so now it's time for the root
    curt = stack.pop();
    if (--k == 0)
        return curt.val;
    //deal with right subtree of the current node
    curt = curt.right;
}
return result;
}

D&C or Binary Search
- 通过计算每一个node的左子树的个数，来知道他是第left+1小的元素
- 这个思路还可以进一步运用在follow up里

public class Solution {
        public int kthSmallest(TreeNode root, int k) {
            int left = nodeCount(root.left);  // this value can be saved in the root node
            if(left + 1 == k) {
                return root.val;
            } else if (left + 1 < k) {
                return kthSmallest(root.right, k - left - 1);
            } else {
                return kthSmallest(root.left, k);
            }
        }

        private int nodeCount(TreeNode root) {
            if(root == null) {
                return 0;
            }
            return 1 + nodeCount(root.left) + nodeCount(root.right);
        }
    }

Follow up: if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine

augmented binary tree，第一次用 O(n) 的时间统计记录一下每个 node 左子树节点个数，后面的每次查询就可以 O(height) 的时间搜索了。也可以用一个HashMap来保存这个count

public class Solution {
      public int kthSmallest(TreeNode root, int k) {
          TreeNodeWithCount rootWithCount = buildTreeWithCount(root);
          return kthSmallest(rootWithCount, k);
      }

      private TreeNodeWithCount buildTreeWithCount(TreeNode root) {
          if (root == null) return null;
          TreeNodeWithCount rootWithCount = new TreeNodeWithCount(root.val);
          rootWithCount.left = buildTreeWithCount(root.left);
          rootWithCount.right = buildTreeWithCount(root.right);
          if (rootWithCount.left != null) rootWithCount.count += rootWithCount.left.count;
          if (rootWithCount.right != null) rootWithCount.count += rootWithCount.right.count;
          return rootWithCount;
      }

      private int kthSmallest(TreeNodeWithCount rootWithCount, int k) {
          if (k <= 0 || k > rootWithCount.count) return -1;
          if (rootWithCount.left != null) {
              if (rootWithCount.left.count >= k) return kthSmallest(rootWithCount.left, k);
              if (rootWithCount.left.count == k-1) return rootWithCount.val;
              return kthSmallest(rootWithCount.right, k-1-rootWithCount.left.count);
          } else {
              if (k == 1) return rootWithCount.val;
              return kthSmallest(rootWithCount.right, k-1);
          }
      }

      class TreeNodeWithCount {
          int val;
          int count;
          TreeNodeWithCount left;
          TreeNodeWithCount right;
          TreeNodeWithCount(int x) {val = x; count = 1;};
      }
  }

Kth Smallest Element in a Sorted Matrix

每次从Heap中poll出来后，将其右侧和下面的node加入
自定义Node类，因为PQ，还需要自己实现Comparator
dx,dy数组，用于往右和往下递增
visited数组，用于记录过已访问过的
加入Heap前要检查是否越界
O(klogk)

class Solution {
  class Node {
      int x;
      int y;
      int val;
      public Node (int val, int x, int y) {
          this.x = x;
          this.y = y;
          this.val = val;
      }
  }
  class NodeComp implements Comparator<Node> {
      public int compare(Node a, Node b) {
          return Integer.compare(a.val, b.val);
      }
  }
  public int kthSmallest(int[][] matrix, int k) {
      int[] dx = {1, 0};
      int[] dy = {0, 1};

      int n = matrix.length;
      int m = matrix[0].length;
      int[][] visited = new int[n][m];

      PriorityQueue<Node> queue = new PriorityQueue<>(k, new NodeComp());

      queue.add(new Node(matrix[0][0], 0, 0));
      int count = 0;
      //也可以用for loop k-1次（0到k-2），而在loop结束后，heap.peek就是我们要的
      while (!queue.isEmpty()) {
          Node node = queue.poll();
          count++;
          if (count == k)
              return node.val;
          for (int i = 0; i < dx.length; i++) {
              int newX = node.x + dx[i];
              int newY = node.y + dy[i];
              if (newX < n && newY < m && visited[newX][newY] == 0) {
                  queue.add(new Node(matrix[newX][newY], newX, newY));
                  visited[newX][newY] = 1;    
              }                
          }
      }

      return -1;
  }   
}

find Kth largest/smallest

Kth Largest Element in an Array

Kth Smallest Element in a BST

Follow up: if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine

Kth Smallest Element in a Sorted Matrix

results matching ""

No results matching ""