12306网站做的好丑,门户网站建设存在问题与不足,电脑安装什么版本wordpress,wordpress 精美主题645. 错误的集合 思路#xff1a;
我们定义一个数组cnt#xff0c;记录每个数出现的次数。然后我们遍历数组#xff0c;从1开始#xff0c;如果cnt[i] 0 那就说明这个是错误的数#xff0c;如果 cnt[i] 2#xff0c;那就说明是重复的数。
代码#xff1a;
class So… 645. 错误的集合 思路
我们定义一个数组cnt记录每个数出现的次数。然后我们遍历数组从1开始如果cnt[i] 0 那就说明这个是错误的数如果 cnt[i] 2那就说明是重复的数。
代码
class Solution {public int[] findErrorNums(int[] nums) {int n nums.length;int[] cnts new int[n 1];for(int i : nums) cnts[i] ;int[] ans new int[2];for(int i 1;i n; i){if(cnts[i] 0) ans[1] i;if(cnts[i] 2) ans[0] i;}return ans;}
} 697. 数组的度 思路
题目说的度是说元素出现的次数的最大值。但是又说最短连续子数组那么我们就要知道数组的长度。我们定义一个Map,key 是数组里的数value是一个数组value[0]是指出现的次数value[1]是指出现的第一次坐标求数组的长度就用最后一次坐标减去第一次出现的坐标。
因为题目说nums.length 从1 开始所以我们定义int[] Max {1, 1}。然后遍历数组如果MAP里没有记录就存下对应的参数如果出现过就把value[0] 1然后和max数组对比。
如果说value[0] max[0]那就把value的信息更新到max如果说value[0] max[0]那么就要看数组的长度
代码
class Solution {public int findShortestSubArray(int[] nums) {// 1、我们需要知道某个数的出现次数// 2、要求最短连续数组所以我们需要知道数组的长度// 3、需要记录的次数、长度和数字本身// 4、长度可以由下表计算保存初始下标// key :数, value[0] 出现的次数, value[1] 第一次下表MapInteger, Integer[] map new HashMap();int[] max {1, 1};for(int i 0; i nums.length; i){if(!map.containsKey(nums[i])){map.put(nums[i],new Integer[] {1, i});}else{Integer[] cur map.get(nums[i]);//出现次数1cur[0] 1;//如果出现的次数比max大或者次数相同但是数组长度更小就更新maxif(cur[0] max[0] || cur[0] max[0] i - cur[1] 1 max[1]){max new int[] {cur[0], i - cur[1] 1};}}}return max[1];}
} 448. 找到所有数组中消失的数字 思路
我们先遍历nums如果 nums[i] i 1那就说明该位置就是对应的数字。
然后遍历nums如果nums[nums[i] - 1] nums[i] 那就说明他不是消失的数字。
如果我们遍历到有重复的数字比如上面的3而且nums[2] 3,那我们就往后遍历。
遍历之后的结果
nums:[1,2,3,4,3,2,7,8]注意题目中的2 3
然后我们再遍历一次nums如果nums[i] ! i 1那就说明他们是消失的数字
代码
class Solution {public ListInteger findDisappearedNumbers(int[] nums) {ListInteger res new ArrayList();int i 0;while(i nums.length){if(nums[i] i 1){i ;continue;}int index nums[i] - 1;if(nums[index] nums[i]){i;continue;}int tmp nums[i];nums[i] nums[index];nums[index] tmp;}for(int j 0; j nums.length; j){if(nums[j] ! j 1){res.add(j 1);}}return res;}
} 442. 数组中重复的数据 思路
我们遍历nums,遍历的每一个元素都变成|x|然后把nums[|x| - 1]的数乘上-1。
再遍历一遍原数组如果当前遍历的元素是负的就说明他是重复的那就说明|x|是重复的。
代码
class Solution {public ListInteger findDuplicates(int[] nums) {int n nums.length;ListInteger ans new ArrayList();for(int i 0; i n; i){int x Math.abs(nums[i]);if(nums[x - 1] 0){nums[x - 1] -nums[x - 1];}else{ans.add(x);}}return ans;}
} 41. 缺失的第一个正数 思路
方法1
对于一个长度为 N 的数组其中没有出现的最小正整数只能在 [1,N1] 中。如果再[1,N]中没有出现那就说明是第N1。
我们遍历数组,如果当前的数小于或者等于0那就让他变成N1,定义int x nums[i],让nums[x - 1]乘上-1。
然后我们遍历数组如果在[1,N]中有没有正数那就说明是N1 如果有那就是第一个正数的坐标1。
代码
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length;for(int i 0; i n; i){if(nums[i] 0) nums[i] n 1;}for(int i 0; i n; i){int x Math.abs(nums[i]);if(x n){nums[x - 1] -Math.abs(nums[x - 1]);}}for(int i 0; i n; i){if(nums[i] 0){return i 1;}}return n 1;}}
方式2
通过置换把对应的数字放到对应的坐标如果当前的数nums[i] ! i 1那就说明i1是缺失的第一个。
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length;for(int i 0; i n; i){while(nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]){int tmp nums[nums[i] - 1];nums[nums[i] - 1] nums[i];nums[i] tmp;}}for(int i 0; i n; i){if(nums[i] ! i 1){return i 1;}}return n 1;}}
