数据结构与队列详解（漫步计算机系统）
问题一：给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
代码如下：
public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
if (k > nums.length || k <= 0)
return new ArrayList<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int num : nums) {
maxHeap.add(num);
if (maxHeap.size() > k)
maxHeap.poll();
}
return new ArrayList<>(maxHeap);
}
算法描述：
- 从头至尾迭代数组；
- 将数组元素压入最大堆maxHeap；
- 若压入的数量超出了K，弹出堆的根元素，即队中最大值元素；
- 迭代结束，堆maxHeap中保存的即为最小的K个元素。
问题二：得到一个数据流中的中位数
代码如下：
/* 大顶堆，存储左半边元素 */
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
/* 小顶堆，存储右半边元素，并且右半边元素都大于左半边 */
private PriorityQueue<Integer> right = new PriorityQueue<>();
/* 当前数据流读入的元素个数 */
private int N = 0;
public void Insert(Integer val) {
/* 插入要保证两个堆存于平衡状态 */
if (N % 2 == 0) {
/* N 为偶数的情况下插入到右半边。
* 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
* 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边 */
left.add(val);
right.add(left.poll());
} else {
right.add(val);
left.add(right.poll());
}
N ;
}
public Double GetMedian() {
if (N % 2 == 0)
return (left.peek() right.peek()) / 2.0;
else
return (double) right.peek();
}
算法描述：
- 设置一个大顶堆left和小顶堆right；
- 当数据流的个数为偶数，将输入的数插入大顶堆left，并将大顶堆的根元素弹出插入小顶堆right；
- 当数据流的个数为奇数，将输入的数插入小顶堆right，并将大顶堆的根元素弹出插入大顶堆left；
- 这样right里面的数都比left里面的数大，若数据流个数为偶数，要获得中位数大小，取left和right根元素的平均值；
- 若数据流个数为奇数，此时right里元素比left里刚好多一个，要获得中位数大小，取right根元素值即可。
问题三：字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时，第一个只出现一次的字符是 "l"。
代码如下：
private int[] cnts = new int[128];
private Queue<Character> queue = new LinkedList<>();
public void Insert(char ch) {
cnts[ch] ;
queue.add(ch);
while (!queue.isEmpty() && cnts[queue.peek()] > 1)
queue.poll();
}
public char FirstAppearingOnce() {
return queue.isEmpty() ? # : queue.peek();
}
算法描述：
- 定义一个128位的整型数组cnts（每个元素代表一个ASCII码字符），以及一个字符型队列queue；
- 每输入一个字符，该字符对应的cnts位元素值加1；
- 将该字符入队列queue；
- 从头至尾迭代队列queue，若队列字符对应的cnts位元素值大于1，队列头元素弹出；
- 此时队列的头元素即为字符流中第一个不重复的字符。
问题四：滑动窗口的最大值
例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。
代码如下：
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> ret = new ArrayList<>();
if (size > num.length || size < 1)
return ret;
PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1); /* 大顶堆 */
for (int i = 0; i < size; i )
heap.add(num[i]);
ret.add(heap.peek());
for (int i = 0, j = i size; j < num.length; i , j ) { /* 维护一个大小为 size 的大顶堆 */
heap.remove(num[i]);
heap.add(num[j]);
ret.add(heap.peek());
}
return ret;
}
算法描述：
- 设置一个最大堆heap，窗口大小为size；
- 先将数组中前size个元素入堆中，得到根元素为第一个窗口的最大值，入最大值链表；
- 将窗口第一个元素从堆中删除，即将窗口向前移动一位；窗口最右边的新元素入堆中，再将此时堆中根元素入最大值链表；
- 迭代至窗口滑动到最右边，返回最大值链表，程序结束。
注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。
