TopK_LRU_归并

1. TopK

 1 import java.util.Comparator;
 2 import java.util.ArrayList;
 3 import java.util.PriorityQueue;
 4 public class Solution {
 5     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
 6         ArrayList<Integer> res = new ArrayList();
 7         if(k<=0 || k > input.length) return res;
 8         //维持一个容量为k的大顶堆
 9         PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
10             @Override
11             public int compare(Integer o1, Integer o2) {
12                 return o2.compareTo(o1);
13             }
14         });
15         for(int i=0;i<input.length;i++){
16             if(maxHeap.size() < k){
17                 maxHeap.offer(input[i]);
18             }else if(input[i] < maxHeap.peek()){
19                 maxHeap.poll();
20                 maxHeap.offer(input[i]);
21             }
22         }
23         for(Integer num : maxHeap){
24             res.add(num);
25         }
26         return res;
27     }
28 }

2. LRU

 1 class LRUCache {
 2     int capacity;
 3     LinkedList<Integer> list = new LinkedList();//存储key的缓存关系，最前面是最近最久未使用的
 4     HashMap<Integer, Integer> map = new HashMap();//存储键值对
 5     public LRUCache(int capacity) {
 6         this.capacity = capacity;
 7     }
 8     public int get(int key) {
 9         if(map.containsKey(key)){
10             list.remove((Integer)key);
11             list.addLast(key);
12             return map.get(key);
13         }
14         return -1;
15     }
16     
17     public void put(int key, int value) {
18         if(map.containsKey(key)){
19             list.remove((Integer)key);
20         }else if(list.size() == capacity){
21             map.remove(list.removeFirst());
22         }
23         map.put(key,value);
24         list.addLast(key);
25     }
26 }

3. 归并排序

基本思想：将待排序序列R[0...n-1]看成n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序表再次归并，得到n/4个长度为4的有序序列；如此反复，最后得到一个长度为n的有序序列。

3.1 总流程

3.2 合并两个小数组

3.3 代码