【LeetCode】面试题总结 消失的数字 最小k个数

 1.消失的数字

两种思路

1.先升序排序，再遍历并且让后一项与前一项比较

2.转化为数学问题求等差数列前n项和 （n的大小为数组的长度），将根据公式求得的应有的和数与数组中实际的和作差

import java.util.*;
class Solution {public int missingNumber(int[] nums) {// 第一种/*Arrays.sort(nums);int len = nums.length;int val = 0;for(int i=0;i<len-1;i++) {if(nums[i+1]!=nums[i]+1) {val = nums[i]+1;break;}}if(val==0) {if(nums[nums.length-1]==nums.length){return 0;}return nums[nums.length-1]+1;}return val;*///第二种int n = nums.length;int sum1 = (n + n*n)/2;int sum2 = 0;for(int i:nums) {sum2 = sum2+i;}return sum1-sum2;}
}

2.最小K个数

用优先级队列（默认情况是小根堆） + 比较器可改变大小根堆 

第一种 ：全部入优先级队列。

第二种 ：先只进入k个数，再依次比较，小的加入，大的删除 这样队列中就一直只有k个元素，节省空间，时间。

总结

找第K大的元素  返回小根堆的根节点的值
找第K小的元素，返回大根堆的节点的值

 

 

import java.util.*;
class IntCmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}
class Solution {public int[] smallestK(int[] arr, int k) {/*  第一种 数组中的数全部入优先级队列int[] ret = new int[k];if(arr.length==0) return ret;PriorityQueue<Integer> queue = new PriorityQueue<>(arr.length);for(int i = 0;i<arr.length;i++) {queue.offer(arr[i]);}for(int j = 0;j<k;j++) {ret[j] = queue.poll();} return ret;*//* 第二种 先只进入k个数，再依次比较，小的加入，大的删除 这样队列中就一直只有k个元素*/  //建立大根堆 使用比较器int[] ret = new int[k];if(arr.length==0 || k<=0) return ret;PriorityQueue<Integer> queue = new PriorityQueue<>(new IntCmp());for(int i=0;i<k;i++) {queue.offer(arr[i]);}for(int j=k;j<arr.length;j++) {int top = queue.peek();if(arr[j] < top) {queue.poll();queue.offer(arr[j]);}}for(int i = 0;i<k;i++) {ret[i] = queue.poll();}return ret;/* 找第K大的元素  返回小根堆的根节点的值找第K小的元素，返回大根堆的节点的值*/ }
}