哪家做网站做的好,网站推广策略含义,跑步机网站建设思维导图,专门做自助游的网站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小的元素返回大根堆的节点的值*/ }
}
