Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
这种解法用到了bucket sort，统计出各个数字出现的次数，再将其加入到对应count的bucket中，最后从后向前便利bucket。
另外可以用heap做，复杂度比这种解法高。

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> valToCount = new HashMap<Integer, Integer>();
        for (int num : nums) {
            valToCount.put(num, valToCount.getOrDefault(num, 0) + 1);
        }
        
        int bucketNumber = 0;
        for (int count : valToCount.values()) {
            bucketNumber = Math.max(bucketNumber, count);
        }
        ArrayList<Integer>[] buckets = (ArrayList<Integer>[]) new ArrayList[bucketNumber];
        for (Map.Entry<Integer, Integer> entry : valToCount.entrySet()) {
            int index = entry.getValue()-1;
            if (buckets[index] == null) {
                buckets[index] = new ArrayList<Integer>();
            }
            buckets[index].add(entry.getKey());
        }
        List<Integer> result = new ArrayList<Integer>();
        for (int i = bucketNumber - 1; i >= 0; i --) {
            if (buckets[i] != null) {
                for (int j = 0; j < buckets[i].size(); j++) {
                    if (k == 0) {
                        break;
                    }
                    k--;
                    result.add(buckets[i].get(j));
                }
            }
        }
        return result;
    }
}

Leetcode: The Skyline Problem & Lintcode: Building Outline

把每一个building拆成两个edge，一个入一个出。所有的edge加入到一个list中。再对这个list进行排序，排序顺序为：如果两个边的position不一样，那么按pos排，否则根据edge是入还是出来排。
根据position从前到后扫描每一个edge，将edge根据是入还是出来将当前height加入或者移除heap。再得到当前最高点来决定是否加入最终结果。非常巧妙，值得思考。

public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> res = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return res;
        }
        List<Edge> edges = new ArrayList<Edge>();
        for (int[] building : buildings) {
            Edge startEdge = new Edge(building[0], building[2], true);
            edges.add(startEdge);
            Edge endEdge = new Edge(building[1], building[2], false);
            edges.add(endEdge);
        }
        //sort edges according to position, height, and if the edge is start or end
        edges.sort(new Comparator<Edge>(){
            public int compare(Edge l1, Edge l2) {
                if (l1.pos != l2.pos)
                    return Integer.compare(l1.pos, l2.pos);
                if (l1.isStart && l2.isStart) {
                    return Integer.compare(l2.height, l1.height);
                }
                if (!l1.isStart && !l2.isStart) {
                    return Integer.compare(l1.height, l2.height);
                }
                return l1.isStart ? -1 : 1;
            }
        });
        //heap of height
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(10, Collections.reverseOrder());
        for (Edge edge : edges) {
            if (edge.isStart) {
                if (heap.isEmpty() || edge.height > heap.peek()) {
                    res.add(new int[]{edge.pos, edge.height});
                }
                heap.add(edge.height);
            } else {
                heap.remove(edge.height);
                if (heap.isEmpty() || edge.height > heap.peek()) {
                    res.add(heap.isEmpty() ? new int[]{edge.pos,0} : new int[]{edge.pos, heap.peek()});
                }
            }
        }
        return res;
    }
    class Edge implements Comparable<Edge>{
        int pos;
        int height;
        boolean isStart;
        public Edge(int pos, int height, boolean isStart) {
            this.pos = pos;
            this.height = height;
            this.isStart = isStart;
        }
    }
}

Lintcode: Kth Smallest Number in Sorted Matrix

最后一个testcase 过不了，memory limit exceeded

public class Solution {
    public int kthSmallest(final int[][] matrix, int k) {
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        PriorityQueue<int[]> heap = new PriorityQueue<int[]>(k, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]);
            }
        });
        heap.add(new int[]{0,0});
        visited[0][0] = true;
        while (k > 1) {
            int[] res = heap.remove();
            int x = res[0];
            int y = res[1];
            
            
            if (x+1 < matrix.length && visited[x+1][y] == false) {
                visited[x+1][y] = true;
                heap.add(new int[]{x+1, y});
            }
            if (y+1 < matrix[0].length && visited[x][y+1] == false) {
                visited[x][y+1] = true;
                heap.add(new int[]{x, y+1});
            }
            k--;
        }
        int[] res = heap.remove();
        return matrix[res[0]][res[1]];
    }
}

Leetcode: Kth Largest Element in an Array

Solution 1: quick select, 复杂度O(n)
题目本身不难，重点是要在递归的时候把参数算对

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findPos(nums, 0, nums.length - 1, k);
    }
    private int findPos(int[] nums, int start, int end, int order) {
    	int pivot = nums[start];
    	int smaller = start;
    	int greater = end + 1;
    	int index = start + 1;
    	while (index < greater) {
    		if (nums[index] <= pivot) {
    			smaller++;
    			index++;
    		} else {
    			int tmp = nums[--greater];
    			nums[greater] = nums[index];
    			nums[index] = tmp;
    		}
    	}
    	index--;
    	nums[start] = nums[index];
    	nums[index] = pivot;
    	if (end - index == order - 1) {
    		return pivot;
    	} else if (end - index < order - 1) {
    		return findPos(nums, start, index - 1, order - (end - index) - 1);
    	} else {
    		return findPos(nums, index + 1, end, order);
    	}
    }
}

Solution 2: 用heap, O(nlgk)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k);
    	for (int num : nums) {
    		if (queue.size() < k) {
    			queue.add(num);
    		} else if (queue.peek()< num) {
    			queue.remove();
    			queue.add(num);
    		}
    	}
        return queue.peek();
    }
}

Lintcode: Sliding Window Maximum

Solution 1: 用heap保存对。虽然能通过OJ，但是复杂度并不对

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	if (nums == null || nums.length == 0 || k <= 0) {
    		return res;
    	}
    	PriorityQueue<Pair> heap = new PriorityQueue<Pair>();
    	for (int i = 0; i < k; i++) {
    		heap.add(new Pair(nums[i], i));
    		//res.add(heap.peek().val);
    	}
    	for (int i = k; i < nums.length; i++) {
    	    res.add(heap.peek().val);
    		Pair toRemove = heap.peek();
    		while (!heap.isEmpty() && heap.peek().index <= i - k) {
    			heap.remove();
    		}
    		heap.add(new Pair(nums[i], i));
    	}
    	res.add(heap.peek().val);
    	return res;
    }
    class Pair implements Comparable<Pair> {
    	int val;
    	int index;
    	public Pair(int val, int index) {
    		this.val = val;
    		this.index = index;
    	}
    	@Override
		public int compareTo(Pair p) {
			return Integer.compare(p.val, val);
		}
    }
}

Solution 2: 用double end queue– Deque.将当前元素加在queue的最后，但是加之前把所有比当前值小的元素从后往前删掉，这样就保证了一个按照index顺序维护的降序queue。非常好的思路。

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	if (nums == null || nums.length == 0 || k <= 0) {
    		return res;
    	}
    	Deque<Integer> dQueue = new LinkedList<Integer>();
    	for (int i = 0; i < k; i++) {
    		while (!dQueue.isEmpty() && nums[dQueue.peekLast()] <= nums[i]) {
    			dQueue.removeLast();
    		}
    		dQueue.addLast(i);
    	}
    	for (int i = k; i < nums.length; i++) {
    	    res.add(nums[dQueue.peekFirst()]);
    		while (!dQueue.isEmpty() && dQueue.peek() <= i - k) {
    			dQueue.removeFirst();
    		}
    		while (!dQueue.isEmpty() && nums[dQueue.peekLast()] <= nums[i]) {
    			dQueue.removeLast();
    		}
    		dQueue.addLast(i);
    	}
    	res.add(nums[dQueue.peekFirst()]);
    	return res;
    }
}

Lintcode: Median II

Numbers keep coming, return the median of numbers at every time a new number added.
Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n-1)/2].
用到了heap，i.e. Java里是priorityqueue，平时很少用到，需要练习。

public class Solution {
    public int[] medianII(int[] nums) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        class maxComparator implements Comparator<Integer> {
            public int compare(Integer a, Integer b) {
                return Integer.compare(b, a);
            }
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(nums.length, new maxComparator());
        int[] result = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            if (minHeap.size() < maxHeap.size()) {
                if (nums[i] < maxHeap.peek()) {
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(nums[i]);
                } else {
                    minHeap.offer(nums[i]);
                }
            } else {
                if (minHeap.size() > 0 && nums[i] > minHeap.peek()) {
                    maxHeap.offer(minHeap.poll());
                    minHeap.offer(nums[i]);
                } else {
                    maxHeap.offer(nums[i]);
                }
            }
            result[i] = maxHeap.peek();
        }
        return result;
    }
}

Lintcode: heapify

Given an integer array, heapify it into a min-heap array.
For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].
基础题，一定要熟练掌握

public class Solution {
    public void heapify(int[] A) {
        for (int i = A.length / 2; i >= 0; i--) {
        	heapify(A, i);
        }
    }

    private void heapify(int[] A, int i) {
    	if (i > A.length) {
    		return;
    	}
    	int left = i * 2 + 1 < A.length ? A[i*2+1] : Integer.MAX_VALUE;
    	int right = i * 2 + 2 < A.length ? A[i*2+2] : Integer.MAX_VALUE;
    	if (left < right && left < A[i]) {
    		A[i*2+1] = A[i];
    		A[i] = left;
    		heapify(A, i*2+1);
    	} else if (right <= left && right < A[i]) {
    		A[i*2+2] = A[i];
    		A[i] = right;
    		heapify(A, i*2+2);
    	}
    }
}

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

---

Solution 1: 简单的分治法。但是leetcode上给了个heap标签，猜想是对k个lists同时sort，维护一个min heap。todo。

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        if (lists.size() == 1) {
            return lists.get(0);
        }
        List<ListNode> result = new ArrayList<ListNode>();
        for (int i = 0; i < lists.size(); i+=2) {
            if (i + 1 < lists.size()) {
                result.add(mergeTwo(lists.get(i), lists.get(i+1)));
            } else {
                result.add(lists.get(i));
            }
        }
        return mergeKLists(result);
    }
    private ListNode mergeTwo(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1), prev = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

Solution 2: use heap. TODO