哪家做网站的公司比较好,免费网络服务器,济南网站建设抖音平台,网站服务器多少钱一年1.消失的数字 两种思路 1.先升序排序#xff0c;再遍历并且让后一项与前一项比较 2.转化为数学问题求等差数列前n项和 #xff08;n的大小为数组的长度#xff09;#xff0c;将根据公式求得的应有的和数与数组中实际的和作差 import java.util.*;
class Solution {public … 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 i0;ilen-1;i) {if(nums[i1]!nums[i]1) {val nums[i]1;break;}}if(val0) {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 sum2i;}return sum1-sum2;}
} 2.最小K个数
用优先级队列默认情况是小根堆 比较器可改变大小根堆
第一种 全部入优先级队列。
第二种 先只进入k个数再依次比较小的加入大的删除 这样队列中就一直只有k个元素节省空间时间。
总结 找第K大的元素 返回小根堆的根节点的值找第K小的元素返回大根堆的节点的值 import java.util.*;
class IntCmp implements ComparatorInteger{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.length0) return ret;PriorityQueueInteger queue new PriorityQueue(arr.length);for(int i 0;iarr.length;i) {queue.offer(arr[i]);}for(int j 0;jk;j) {ret[j] queue.poll();} return ret;*//* 第二种 先只进入k个数再依次比较小的加入大的删除 这样队列中就一直只有k个元素*/ //建立大根堆 使用比较器int[] ret new int[k];if(arr.length0 || k0) return ret;PriorityQueueInteger queue new PriorityQueue(new IntCmp());for(int i0;ik;i) {queue.offer(arr[i]);}for(int jk;jarr.length;j) {int top queue.peek();if(arr[j] top) {queue.poll();queue.offer(arr[j]);}}for(int i 0;ik;i) {ret[i] queue.poll();}return ret;/* 找第K大的元素 返回小根堆的根节点的值找第K小的元素返回大根堆的节点的值*/ }
}
