Geneal

130t Heapify

Given an integer array, heapify it into a min-heap array. Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

• Starting from middle of array, sink the node in reverse order

Reference

private void sink(int[] A, int i){
    // while 直到右邊沒有node  
    while(i*2+1 < A.length){
        int small = i*2+1;
        // 若right tree存在, 比較左右tree大小
        if (i*2+2 < A.length && A[small] > A[i*2+2]){
            small = i*2+2;
        }
        // 比較node跟small 大小
        if (A[small] >= A[i]){
            break;
        }

        // lift small number up
        int tmp = A[small];
        A[small] = A[i];
        A[i] = tmp;
        i = small; 
    }
}
public void heapify(int[] A) {
    for (int i= (A.length-1)/2; i>=0; i--){
        sink(A, i);
    }
}

88 Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

比較兩個list最後element大小, 較大擺在後面

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
  
    idx1, idx2, idx_write = m-1, n-1, m+n-1
    
    while idx1 >= 0 and idx2 >= 0:
        if nums1[idx1] > nums2[idx2]:
            nums1[idx_write] = nums1[idx1]
            idx1 -= 1
        else:
            nums1[idx_write] = nums2[idx2]
            idx2 -= 1
        idx_write -= 1
        
    while idx2 >= 0:
        nums1[idx_write] = nums2[idx2]
        idx2 -= 1 
        idx_write -= 1

Merge Sorted Array II

Brute force O(nlogn), concatenate and sorted Better sol: O(nlogk), k is the heap number

1. class Node with "arrayNum" and "value"

2. Make arrays into a list of iters

3. Create k min heap with the heads of iterators

4. While heap is not empty, add to list

public static class node {
    public Integer arrayNum;
    public Integer value;

    node(Integer arrayNum, Integer value){
        this.arrayNum = arrayNum;
        this.value = value;
    }
}


public class MergeSortedArray {
    public static List<Integer> mergeSortedArray(List<List<Integer>> sortedArrays){
        List<Integer> result = new ArrayList<>();
        List<Iterator<Integer>> iters = new ArrayList<>();
        for (List<Integer> array: sortedArrays){
            iters.add(array.iterator());
        }

        PriorityQueue<node> minheap = new PriorityQueue<>(sortedArrays.size(), n1.value - n2.value);
            }
        });

        for (int i = 0; i < iters.size(); i++){
            if (iters.get(i).hasNext()){
                minheap.add(new node(i, iters.get(i).next())); //保證每個iterator都會輪到
            }
        }

        while(!minheap.isEmpty()){
            node entry = minheap.poll();
            result.add(entry.value);
            if (iters.get(entry.arrayNum).hasNext()){ //檢查iterator是否為空
                minheap.add(new node(entry.arrayNum, iters.get(entry.arrayNum).next()));
            }
        }
        return result;
    }
}

23 Merge k Sorted LinkedList

• Time O(nlogk), Space O(n*k)

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    Queue<ListNode> minHeap = new PriorityQueue<>((a,b) -> a.val - b.val);
    for(ListNode n: lists){
        if(n != null) minHeap.add(n);
    }
    
    while(!minHeap.isEmpty()){
        ListNode node = minHeap.poll();
        cur.next = new ListNode(node.val);
        cur = cur.next;
        node = node.next;
        if(node != null){
            minHeap.add(node);
        }
    }
    return dummy.next;     
}

• Time O(nlogk), Space O(1)

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists: return None
    inter = 1
    total = len(lists)
    
    while inter < total:
        for i in range(0, total - inter, inter*2):
            lists[i] = self.merge2List(lists[i], lists[i+inter])
        inter *= 2
    
    return lists[0]

def merge2List(self, l1, l2):
    dummy = cur = ListNode(0)
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    if l1:
        cur.next = l1
    if l2:
        cur.next = l2
    return dummy.next

295 Find median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

• Use 2 heaps, a maxHeap to store left half data, a minHeap to store right half data

• A boolean flag to record odd or even

• Time: O(logn)

class MedianFinder {
    Queue<Integer> lo;
    Queue<Integer> hi;
    boolean isOdd;
    /** initialize your data structure here. */
    public MedianFinder() {
        lo = new PriorityQueue<>(1, (a,b) -> b-a);
        hi = new PriorityQueue<>();
    }

    public void addNum(int num) {
        lo.add(num);
        int max = lo.poll();
        hi.add(max);
        isOdd = false;
        if (hi.size() > lo.size()){
            lo.add(hi.poll());
            isOdd = true;
        }
    }

    public double findMedian() {
        if (isOdd){
            return lo.peek();
        }else{
            return ((double)lo.peek() + (double)hi.peek()) / 2;
        } 
    }
}

253. Meeting Rooms II

find the minimum number of conference rooms required.

1. Sort the intervals by inter.start time

2. Put 1st inter.end in the heap

3. Peak pre ending time and current start time to determine to pop a room

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    if not intervals: return 0
    intervals.sort(key=lambda x:x.start)

    heap = []
    heapq.heappush(heap, intervals[0].end)

    for interval in intervals[1:]:
        if interval.start >= heap[0]:
            heapq.heappop(heap)

        heapq.heappush(heap, interval.end)

    return len(heap)