Heap
2018-12-13 本文已影响0人
谢谢水果
相关Java知识
1. 新建堆 默认是最小堆
PriorityQueue操作时间复杂度：
add: O(logn);
heap本身支持O(logn)的remove 但是PriorityQueue的remove是O(n);
pop: O(logn)
peek: O(1)
Queue<Integer> heap = new PriorityQueue<>();
2. 自定义排序规则 下例是ListNode的最小堆
private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>(){
public int compare(ListNode left, ListNode right){
return left.val-right.val;
}
};
Queue<ListNode> heap = new PriorityQueue<>(lists.length, ListNodeComparator);
3. 也可以implements Comparable接口
Queue<Point> minHeap = new PriorityQueue();
class Point implements Comparable<Point>{
int x;
int y;
int val;
Point(int x, int y, int val){
this.x = x;
this.y = y;
this.val = val;
}
@Override
public int compareTo(Point b){
return this.val-b.val;
}
}
4. 如果不是自定义类型的话 可以直接这样建最大堆
maxHeap = new PriorityQueue(Collections.reverseOrder());
题目
- 264 Ugly Number II 两种方法：用堆O(nlogn)/利用丑数的特性一个一个算出来O(n)
- 263 Ugly Number
- 23 Merge k Sorted Lists 三种做法 heap merge divideconque 都是O(N*logk) N是所有元素总数 k是lists总数
topK类问题
topK两种思路：
1 离线算法 用quick select O(n)时间选出第k大的数 然后在O(n)时间扫描一下把小于这个数的所有数选出来 总时间复杂度O(n) 如果排序就O(n)+O(klogk)
2 在线算法 用max heap O(nlogn+klogn); 更好的方法是用min heap O(nlogk)
找大的就用最小堆 每次剔除最小的； 找最近的就用最大堆 每次剔除最近的
第k大的
- 703 Kth Largest in a Stream(online) 215 Kth Largest in an Array(offline)
前k大的 - 545 Top k Largest Numbers II(online) 544 Top k Largest Numbers(offline) (详见双指针quick sort篇)
- 前k近的 658 Find K Closest Elements
- 用maxheap O(nlogk)
- 因为是找距离target最近的k个 所以可以排序 然后binarysearch到第一个比target小的位置 然后左右双指针一一添加 排序O(nlogn) + binarySearch O(logn) + 找k个 k
- 613 High Five
- 给一个Record数组(id score) 返回每个学生最高5个分数的平均分 为每个学生建一个堆
- 295 Find Median from Data Stream
- 挺有意思的这个题 建两个堆minHeap maxHeap，维持minHeap中元素都大于等于maxHeap中的元素，且元素差小于二 logn to insert, O(1) to query
- 378 Kth Smallest Element in a Sorted Matrix
- heap 一行或者一列扔进堆 取出一个然后把同列或同行的下一个扔进去 k(logk)
- 二分法
- 373 Find K Pairs with Smallest Sums
264. Ugly Number II
class Solution {
public int nthUglyNumber(int n) {
return nMethod(n);
return nlognMethod(n);
}
public int nlognMethod(int n) {
Queue<Integer> heap = new PriorityQueue<>();
Set<Integer> set = new HashSet<>();
heap.add(1);
set.add(1);
int[] ugly = {2, 3, 5};
while(n>1){
int top = heap.poll();
for(int i=0; i<3; i++){
int next = top*ugly[i];
if(next/ugly[i]!=top)
continue;
if(!set.contains(next)){
set.add(next);
heap.offer(next);
}
}
n = n-1;
}
return heap.peek();
}
public int nMethod(int n) {
int[] ugly = new int[n];
ugly[0] = 1;
int index2 = 0, index3 = 0, index5 = 0;
int factor2 = 2, factor3 = 3, factor5 = 5;
for(int i=1;i<n;i++){
int min = Math.min(Math.min(factor2,factor3),factor5);
ugly[i] = min;
if(factor2 == min)
factor2 = 2*ugly[++index2];
if(factor3 == min)
factor3 = 3*ugly[++index3];
if(factor5 == min)
factor5 = 5*ugly[++index5];
}
return ugly[n-1];
}
}
263 Ugly Number
class Solution {
public boolean isUgly(int num) {
if(num==0)
return false;
while(num%2==0)
num = num/2;
while(num%3==0)
num = num/3;
while(num%5==0)
num = num/5;
return num==1;
}
}
23 Merge k Sorted Lists 三种做法 heap merge divideconque
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>(){
public int compare(ListNode left, ListNode right){
return left.val-right.val;
}
};
public ListNode mergeKLists(ListNode[] lists) {
return heapMethod(lists);
// return mergeMethod(lists);
}
private ListNode heapMethod(ListNode[] lists){
if(lists==null || lists.length==0)
return null;
Queue<ListNode> heap = new PriorityQueue<>(lists.length, ListNodeComparator);
for(int i=0; i<lists.length; i++){
if(lists[i]!=null)
heap.offer(lists[i]);
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while(!heap.isEmpty()){
ListNode next = heap.poll();
current.next = next;
current = next;
if(next.next!=null)
heap.offer(next.next);
}
return dummy.next;
}
private ListNode mergeMethod(ListNode[] lists){
if(lists==null || lists.length==0)
return null;
return mergelist(lists, 0, lists.length-1);
}
private ListNode mergelist(ListNode[] lists, int start, int end){
if(start>=end)
return lists[start];
int mid = start+(end-start)/2;
ListNode left = mergelist(lists, start, mid);
ListNode right = mergelist(lists, mid+1, end);
return merge(left, right);
}
private ListNode merge(ListNode left, ListNode right){
ListNode dummy = new ListNode(0);
ListNode node = dummy;
while(left!=null && right!=null){
if(left.val<=right.val){
node.next = left;
left=left.next;
node = node.next;
}else{
node.next = right;
right = right.next;
node = node.next;
}
}
while(left!=null){
node.next = left;
left = left.next;
node = node.next;
}
while(right!=null){
node.next = right;
right = right.next;
node = node.next;
}
return dummy.next;
}
}
703. Kth Largest Element in a Stream
class KthLargest {
Queue<Integer> heap;
int k;
public KthLargest(int k, int[] nums) {
heap = new PriorityQueue<>(k);
this.k = k;
for(int i=0; i<nums.length; i++){
heap.offer(nums[i]);
if(heap.size()>k)
heap.poll();
}
}
public int add(int val) {
heap.offer(val);
if(heap.size()>k)
heap.poll();
return heap.peek();
}
}
215. Kth Largest Element in an Array
- quickselect O(n)
- heap O(nlogK)
class Solution {
public int findKthLargest(int[] nums, int k) {
// return heap(nums, k);
return partition(nums, k);
}
public int heap(int[] nums, int k) {
if(nums==null || k<=0 || nums.length<k)
return -1;
PriorityQueue<Integer> heap = new PriorityQueue<>(k);
for(int i=0; i<nums.length; i++){
if(heap.size()<k)
heap.offer(nums[i]);
else{
heap.offer(Math.max(nums[i], heap.poll()));
}
}
return heap.peek();
}
public int partition(int[] nums, int k) {
if(nums==null || k<=0 || nums.length<k)
return -1;
return helper(nums, k, 0, nums.length-1);
}
private int helper(int[] nums, int k, int start, int end){
if(start>=end)
return nums[start];
int left = start;
int right = end;
int mid = left+(right-left)/2;
int pivot = nums[mid];
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(k<=right-start+1){
return helper(nums, k, start, right);
}
if(k>=left-start+1)
return helper(nums, k-(left-start), left, end);
return nums[right+1];
}
}
545. Top k Largest Numbers II
public class Solution {
Queue<Integer> heap;
int k;
/*
* @param k: An integer
*/public Solution(int k) {
// do intialization if necessary
heap = new PriorityQueue<>(k);
this.k = k;
}
/*
* @param num: Number to be added
* @return: nothing
*/
public void add(int num) {
// write your code here
heap.offer(num);
if(heap.size()>k)
heap.poll();
}
/*
* @return: Top k element
*/
public List<Integer> topk() {
// write your code here
List<Integer> result = new ArrayList<>();
Iterator it = heap.iterator();
while(it.hasNext()){
result.add((Integer)it.next());
}
Collections.sort(result, Collections.reverseOrder());
return result;
}
}
544. Top k Largest Numbers
public class Solution {
/**
* @param nums: an integer array
* @param k: An integer
* @return: the top k largest numbers in array
*/
public int[] topk(int[] nums, int k) {
// write your code here
int kth = findKthLargest(nums, k, 0, nums.length-1);
int[] result = new int[k];
int left=0;
int right = k-1;
System.out.println(kth);
for(int i=0; i<nums.length; i++){
if(nums[i]>kth){
result[left] = nums[i];
left++;
}
if(nums[i]==kth&&right>=left){
result[right] = nums[i];
right--;
}
}
Arrays.sort(result);
int start = 0;
int end = k-1;
while(start<end){
int temp = result[start];
result[start] = result[end];
result[end] = temp;
start++;
end--;
}
return result;
}
private int findKthLargest(int[] nums, int k, int start, int end){
if(start>=end)
return nums[start];
int mid = start + (end-start)/2;
int pivot = nums[mid];
int left = start;
int right = end;
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 findKthLargest(nums, k, start, right);
if(start+k-1>=left)
return findKthLargest(nums, k-(left-start), left, end);
return nums[right+1];
}
}
// base on heap
class Solution {
/*
* @param nums an integer array
* @param k an integer
* @return the top k largest numbers in array
*/
public int[] topk(int[] nums, int k) {
PriorityQueue<Integer> minheap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
for (int i : nums) {
minheap.add(i);
if (minheap.size() > k) {
minheap.poll();
}
}
int[] result = new int[k];
for (int i = 0; i < result.length; i++) {
result[k - i - 1] = minheap.poll();
}
return result;
}
};
// base on quicksort
import java.util.Random;
class Solution {
/*
* @param nums an integer array
* @param k an integer
* @return the top k largest numbers in array
*/
public int[] topk(int[] nums, int k) {
// Write your code here
quickSort(nums, 0, nums.length - 1, k);
int[] topk = new int[k];
for (int i = 0; i < k; ++i)
topk[i] = nums[i];
return topk;
}
private void quickSort(int[] A, int start, int end, int k) {
if (start >= k)
return;
if (start >= end) {
return;
}
int left = start, right = end;
// key point 1: pivot is the value, not the index
Random rand =new Random(end - start + 1);
int index = rand.nextInt(end - start + 1) + start;
int pivot = A[index];
// key point 2: every time you compare left & right, it should be
// left <= right not left < right
while (left <= right) {
// key point 3: A[left] < pivot not A[left] <= pivot
while (left <= right && A[left] > pivot) {
left++;
}
// key point 3: A[right] > pivot not A[right] >= pivot
while (left <= right && A[right] < pivot) {
right--;
}
if (left <= right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left++;
right--;
}
}
quickSort(A, start, right, k);
quickSort(A, left, end, k);
}
};
658. Find K Closest Elements
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int target) {
return maxHeap(arr, k, target);
//return binarySearch(arr, k, target);
}
private List<Integer> maxHeap(int[] arr, int k, int target){
Queue<Integer> heap = new PriorityQueue<>(k+1, new Comparator<Integer>(){
public int compare(Integer x, Integer y){
int diff = -Math.abs(x-target)+Math.abs(y-target);
if(diff!=0)
return diff;
return y-x;
}
});
for(int i=0; i<arr.length; i++){
heap.offer(arr[i]);
if(heap.size()>k)
heap.poll();
}
List<Integer> temp = new ArrayList<>();
for(int i=0; i<k; i++){
temp.add(heap.poll());
}
Collections.sort(temp);
return temp;
}
public List<Integer> binarySearch(int[] arr, int k, int target) {
List<Integer> result = new ArrayList<>();
if(arr==null || arr.length<k)
return null;
int left = 0;
int right = arr.length-1;
while(left+1<right){
int mid = left+(right-left)/2;
if(target<=arr[mid])
right = mid;
else
left = mid;
}
if(arr[right]<target){
left = right;
right = right+1;
}
else if(arr[left]<target)
left = left;
else{
left = -1;
right = 0;
}
while(k>0){
if(left<0)
right++;
else if(right>arr.length-1)
left--;
else{
if(target-arr[left]>arr[right]-target)
right++;
else
left--;
}
k--;
}
for(int i=left+1; i<right; i++){
result.add(arr[i]);
}
return result;
}
}
613 High Five
public class Solution {
/**
* @param results a list of <student_id, score>
* @return find the average of 5 highest scores for each person
* Map<Integer, Double> (student_id, average_score)
*/
public Map<Integer, Double> highFive(Record[] results) {
// Write your code here
Map<Integer, Double> result = new HashMap<>();
Map<Integer, PriorityQueue<Integer>> scoreHeaps = new HashMap<>();
for(Record record: results){
int id = record.id;
int score = record.score;
PriorityQueue<Integer> heap = scoreHeaps.getOrDefault(id,new PriorityQueue<Integer>(5));
heap.offer(score);
if(heap.size()>5)
heap.poll();
scoreHeaps.put(id, heap);
}
for(Integer id : scoreHeaps.keySet()){
PriorityQueue<Integer> heap = scoreHeaps.get(id);
Iterator it = heap.iterator();
int sum = 0;
while(it.hasNext()){
sum = sum+(int)it.next();
}
double average = (double) sum/heap.size();
System.out.println(average);
result.put(id, average);
}
return result;
}
}
- 295 Find Median from Data Stream
logn to insert, O(1) to query
class MedianFinder {
Queue<Integer> minHeap;
Queue<Integer> maxHeap;
/** initialize your data structure here. */
public MedianFinder() {
minHeap = new PriorityQueue();
maxHeap = new PriorityQueue(Collections.reverseOrder());
}
public void addNum(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if(minHeap.size()>maxHeap.size()+1)
maxHeap.offer(minHeap.poll());
}
public double findMedian() {
if(minHeap.size()==maxHeap.size())
return (double)(minHeap.peek()+maxHeap.peek())/2;
return minHeap.peek();
}
}
- 378 Kth Smallest Element in a Sorted Matrix
class Solution {
public int kthSmallest(int[][] matrix, int k) {
Queue<Point> minHeap = new PriorityQueue();
for(int i=0; i<matrix.length; i++){
Point point = new Point(i, 0, matrix[i][0]);
minHeap.offer(point);
}
int count = 1;
while(count<k){
Point point = minHeap.poll();
count++;
if(point.y==matrix[0].length-1)
continue;
Point next = new Point(point.x, point.y+1, matrix[point.x][point.y+1]);
minHeap.offer(next);
}
return minHeap.peek().val;
}
class Point implements Comparable<Point>{
int x;
int y;
int val;
Point(int x, int y, int val){
this.x = x;
this.y = y;
this.val = val;
}
@Override
public int compareTo(Point b){
return this.val-b.val;
}
}
}
- 373 Find K Pairs with Smallest Sums
