第一题：645. 错误的集合
集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1: 输入: nums = [1,2,2,4] 输出: [2,3]
注意：
给定数组的长度范围是 [2, 10000]。 给定的数组是无序的。
思路：
正确的思路1： 做题目一定要先自己手写一个大概思路，不然真正写代码的时候，人会傻的！ 1、先对数组进行排序 2、循环遍历数组，当nums[i+1] == nums[i]的时候，就break，然后得到nums[i]就是重复的那个 3、先考虑一种特殊情况就是：[1,2,2,3,4,5],这个缺的是6，特殊写一个分支 4、然后继续循环从1开始，当nums[i] >nums[i-1]+1的时候，就返回nums[i-1]+1，是缺的那个
代码一：
public int[] findErrorNums(int[] nums) {
Arrays.sort(nums);//先对数组进行排序
int lack = 1; //定义缺少的值默认为1，默认缺的是第一个数：1，这个地方很巧妙
int doubles = 0; //定义重复的数为0
//这个考虑一种特殊情况就是：[1,2,2,3,4,5],这个缺的是6，特殊写一个分支，就是当缺的是最后一个时，单独考虑
if(nums[nums.length-1] != nums.length){
lack = nums.length;
}else {
for (int i = 1; i < nums.length; i++) {
if(nums[i] >nums[i-1]+1){ //nums[i] >nums[i-1]+1这个条件很重要，就是[1,2,2,3,5],缺的是4，那5>3+1
lack = nums[i-1]+1;
break;
}
}
}
//求重复的数还是简单：当你后面的等于前面的就说明重复了，返回前面的nums[i]就好了
for (int i = 0; i < nums.length; i++) {
if(nums[i+1] == nums[i]){
doubles = nums[i];
break;
}
}
return new int []{doubles,lack};
}简洁版本：
public class Solution {
public int[] findErrorNums(int[] nums) {
Arrays.sort(nums);
int dup = -1, missing = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1])
dup = nums[i];
else if (nums[i] > nums[i - 1] + 1)
missing = nums[i - 1] + 1;
}
return new int[] {dup, nums[nums.length - 1] != nums.length ? nums.length : missing};
}
}
我的错误思路： 我刚开始就是这个想法做的，但是在缺项那个条件那里卡住了，我想的是元素nums[i] != i+1,然后返回i+1,这是错误的想法，自己还是要多思考。
正确的思路2：暴力解法 直接的做法就是单独检查 1 到 n的所有数字。 在检查每个数字时都遍历整个nums 数组，检查当前数字在 nums 中是否出现了两次，或者一次都没有出现。 使用 dup 和 missing 记录重复数字和缺失数字。
public class Solution {
public int[] findErrorNums(int[] nums) {
int dup = -1, missing = -1;
for (int i = 1; i <= nums.length; i++) {
int count = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] == i)
count++;
}
if (count == 2)
dup = i;
else if (count == 0)
missing = i;
}
return new int[] {dup, missing};
}
}正确的思路3：优化的暴力解法 在 方法一 中，即使已经找到了重复数字和缺失数字，依然会继续查找。但是根据问题描述，只有一个重复数字和缺失数字，因此一旦找到这两个数字，就可以提前结束查找过程。
public class Solution {
public int[] findErrorNums(int[] nums) {
int dup = -1, missing = -1;;
for (int i = 1; i <= nums.length; i++) {
int count = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] == i)
count++;
}
if (count == 2)
dup = i;
else if (count == 0)
missing = i;
if (dup > 0 && missing > 0)
break;
}
return new int[] {dup, missing};
}
}
正确的思路4：使用异或运算 思考一个简单的问题，一个长度为 n-1n−1 的数组包含 11 到 nn 中的 n-1n−1 个数字，有一个数字缺失，如何找出这个缺失的数字。首先使用 11 到 nn 的所有数字做异或运算，然后再使用数组中的所有数字与这个数字异或，最后得到的值就是缺失数字。因为数字与其本身做异或运算结果为 0，因此所有数字做完异或后，剩余的就是缺失的数字。 按照这个方法，将 numsnums 中所有的数字与 11 到 nn 的所有数字做异或运算，得到的结果为 x^y，x 和 y 分别表示 numsnums 中重复数字和缺失数字。 在异或结果 xorxor 的二进制中，值为 1 的位置表示 xx 和 yy 在该位置的值不同，值为 0 的位置表示 x 和 y 在该位置的值相同。我们称 xorxor 最右边比特位为 rightmostbitrightmostbit，且使该位置为 1。 根据 rightmostbitrightmostbit 不同将数组 numsnums 分为两部分。第一部分所有数字的 rightmostbitrightmostbit 为 1，第二部分所有数字的 rightmostbitrightmostbit 为 0。那么 x 和 y会被分配到不同的部分。此时问题就简化为最开始的简单问题。 根据 rightmostbitrightmostbit 的不同，将 11 到 nn 的所有元素分为两部分。 现在分别使用从 numsnums 中分出来 rightmostbitrightmostbit 为 1 的部分与 11 到 nn 中分出来 rightmostbitrightmostbit 为 1 的部分做异或。在结果中，相同的元素异或为 0，最终只会剩下重复数字或缺失数字，即 xx 或 yy。同理也对 rightmostbitrightmostbit 为 0 的部分异或。 最后遍历 numsnums，确定两个数字中哪个为重复数字，哪个为缺失数字。
public class Solution {
public int[] findErrorNums(int[] nums) {
int xor = 0, xor0 = 0, xor1 = 0;
for (int n: nums)
xor ^= n;
for (int i = 1; i <= nums.length; i++)
xor ^= i;
int rightmostbit = xor & ~(xor - 1);
for (int n: nums) {
if ((n & rightmostbit) != 0)
xor1 ^= n;
else
xor0 ^= n;
}
for (int i = 1; i <= nums.length; i++) {
if ((i & rightmostbit) != 0)
xor1 ^= i;
else
xor0 ^= i;
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] == xor0)
return new int[]{xor0, xor1};
}
return new int[]{xor1, xor0};
}
}第二题：697. 数组的度
给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1: 输入: [1, 2, 2, 3, 1] 输出: 2 解释: 输入数组的度是2，因为元素1和2的出现频数最大，均为2. 连续子数组里面拥有相同度的有如下所示: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] 最短连续子数组[2, 2]的长度为2，所以返回2.
示例 2: 输入: [1,2,2,3,1,4,2] 输出: 6
注意: nums.length 在1到50,000区间范围内。 nums[i] 是一个在0到49,999范围内的整数。
思路：
具有度数 d 的数组必须有一些元素 x 出现 d 次。如果某些子数组具有相同的度数，那么某些元素 x （出现 d 次）。最短的子数组是将从 x 的第一次出现到最后一次出现的数组。 对于给定数组中的每个元素，让我们知道 left 是它第一次出现的索引； right 是它最后一次出现的索引。例如，当 nums = [1,2,3,2,5] 时，left[2] = 1 和 right[2] = 3。 然后，对于出现次数最多的每个元素 x，right[x] - left[x] + 1 将是我们的候选答案，我们将取这些候选的最小值。
具体步骤：
第一：先找到出现频数最大的那个数x，求出度为？ 第二：找出每个元素第一次出现的下标left 第三：找到每个元素最后出现的下标right 第四：结果为right-left+1
代码：
class Solution {
public int findShortestSubArray(int[] nums) {
// 如果数组是一个空数组或者数组不空，但是里面没有任何元素，那就返回0
if(nums == null || nums.length == 0){
return 0;
}
// 1、如果数组就1个元素，数组的度就是1，
// 2、包含这个度1的数组长度的最小值，这个数组长度本身了，就是这个1，因此返回1
if(nums.length == 1){
return 1;
}
// map1用来统计数组中每个元素出现的次数
// 比如题中：1 -> 2 (数组中1出现了2次)
// 2 -> 2 (数组中2出现了2次)
// 3 -> 1 (数组中3出现了1次)
Map<Integer, Integer> map1 = new HashMap<>();
// map2用来记录数组中元素第一次出现时的位置（索引）
// 比如题中：1 -> 0 (数组中1第一次出现的位置是0)
// 2 -> 1 (数组中2第一次出现的位置是1)
// 3 -> 3 (数组中3第一次出现的位置是3)
Map<Integer, Integer> map2 = new HashMap<>();
// map3用来记录数组相同元素，第一次出现与最后一次出现之间的长度
// 比如题中：元素1第一次出现的位置是0，最后一次出现的位置是4，它们之间的长度 = 5
// 元素2第一次出现的位置是1，最后一次出现的位置是2，它们之间的长度 = 3
// 元素3第一次出现的位置是3，最后一次出现的位置是3，它们之间的长度 = 1
Map<Integer, Integer> map3 = new HashMap<>();
for(int i = 0; i < nums.length; i++){
// map1用来统计数组中每个元素出现的次数，key = 数组元素， value = 出现的次数
map1.put(nums[i], map1.getOrDefault(nums[i],0) + 1);
// map2用来记录数组中元素第一次出现时的位置（索引），key = 数组元素， value = 第一次出现的位置（索引）
if(!map2.containsKey(nums[i])){
map2.put(nums[i],i);
}
// map3用来记录数组相同元素，第一次出现与最后一次出现之间的长度，key = 数组元素， value = 第一次出现与最后一次出现之间的长度
// 数组元素第一次出现的位置保存在map2中，可以从里面拿出来
map3.put(nums[i],i - map2.get(nums[i]) + 1);
}
// maxCount用来记录数组的度
int maxCount = 0;
// map1中存了数组元素的次数，将出现次数的最大值取出来，放到maxCount中
for(int num : map1.values()){
maxCount = Math.max(maxCount, num);
}
// minLength用来记录最终的答案，保存最短连续子数组的长度，初始化为最大值
// minLength是用来保存最小值的，将其初始化为最大值，才能不断更新，得到更小的，再更新得到更小的，最终得到的是最小的
int minLength = Integer.MAX_VALUE;
for(int key : map1.keySet()){
// 如果有多个数组元素，它们的度都是maxCount，则选择长度最小的数组元素，
// 以这个数组元素为key，获取其第一次出现与最后一次出现之间的长度，其长度保存在map3当中
if(maxCount == map1.get(key)){
minLength = Math.min(minLength, map3.get(key));
}
}
return minLength;
}
}收获：
1、学会使用javaAPI来解决问题，比如map这类结构 2、思路清晰，先列草稿来大概理清思路，然后再动笔实现 3、大胆猜测，然后再去证明
第三题：448. 找到所有数组中消失的数字
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例: 输入: [4,3,2,7,8,2,3,1] 输出: [5,6]
思路：
思路1：使用外部结构hashmap 循环数组，然后将数组值nums[i]做为map的key，然后至于map的value其实无所谓，就用Boolean表示即可 然后从1遍历到数组长度n，去看map中的key是否包含了i，没包含就说明缺少了，返回放入list中。 官方讲解： ·我们用一个哈希表 hash 来记录我们在数组中遇到的数字。我们也可以用集合 set 来记录，因为我们并不关心数字出现的次数。 ·然后遍历给定数组的元素，插入到哈希表中，即使哈希表中已经存在某元素，再次插入了也会覆盖 ·现在我们知道了数组中存在那些数字，只需从 1⋯N 范围中找到缺失的数字。 ·从 1⋯N 检查哈希表中是否存在，若不存在则添加到存放答案的数组中。
public List<Integer> findDisappearedNumbers(int[] nums) {
//第一步：循环数组，然后将数组值nums[i]做为map的key
Map<Integer,Boolean> map = new HashMap<>();
for(Integer num : nums){
if(!map.containsKey(num)){ //只有当map中没得才添加，有了就不要添加了
map.put(num,true);
}
}
//从1遍历到数组长度n，去看map中的key是否包含了i
List<Integer> result = new LinkedList<>();
for (int i = 1; i <= nums.length; i++) {
if(!map.containsKey(i)){
result.add(i) ;
}
}
return result;
}思路2：抽屉法，原地置换法 1、遍历数组，得到每一个元素对应的那个下标（|nums[i]|-1）（就是nums[0]的绝对值-1作为新的下标） 2、当那个下标的值大于0，那我就将它置为相反数（负数） 3、然后遍历数组，当数组中存在大于0的，那就说明nums[i]的i+1的值就是答案！ 官方讲解： ·遍历输入数组的每个元素一次。 ·我们将把 |nums[i]|-1 索引位置的元素标记为负数。即nums[∣nums[i]∣−1]×−1 。 ·然后遍历数组，若当前数组元素 nums[i] 为负数，说明我们在数组中存在数字 i+1。
public List<Integer> findDisappearedNumbers2(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i])-1; //遍历数组，得到每一个元素对应的那个下标
if(nums[index]>0){
nums[index] = nums[index] * (-1); //当那个下标的值大于0，那我就将它置为相反数（负数）
}
}
List<Integer> result = new LinkedList();
for (int i = 0; i < nums.length; i++) {
if(nums[i] >0){
result.add(i+1); //然后遍历数组，当数组中存在大于0的，那就说明nums[i]的i+1的值就是答案！
}
}
return result;
}第四题：442. 数组中重复的数据
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例： 输入: [4,3,2,7,8,2,3,1] 输出: [2,3]
思路：
这也能算是中等题目？就这？（我瞎逼逼的哈，我膨胀了） 一看到这个题目就要想到使用hashmap或者原地置换方法 1、遍历数组 2、找到每一个元素对应的置换下标：int newIndex = Math.abs(nums[i]) -1; 3、如果位置newIndex 上的数字已经为负，则newIndex+1是出现两次的数字 原地置换做为数组类题目中常见的方法，一定要经常复习哦！
代码：
public List<Integer> findDuplicates(int[] nums) {
List<Integer> list = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
int newIndex = Math.abs(nums[i]) -1; //找到每一个元素对应的置换下标
if(nums[newIndex] <0){ //如果位置newIndex 上的数字已经为负，则newIndex+1是出现两次的数字
list.add(newIndex+1);
}else {
nums[newIndex] *= -1; //否则就置为负数
}
}
return list;
}第五题：41. 缺失的第一个正数
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1: 输入: [1,2,0] 输出: 3
示例 2: 输入: [3,4,-1,1] 输出: 2
示例 3: 输入: [7,8,9,11,12] 输出: 1
提示： 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
思路：
本人愚见： 1、先排好序 2、然后控制数组从第一个正整数开始（用Linkedlist来实现） 3、然后对Linkedlist去重处理 4、从1开始遍历到list的长度；然后list里面的元素也开始遍历，当不相等的时候就是缺的那个 本人在去重的那个地方花了很多时间，而且这个思路还不符合规矩，时间和空间复杂度不符合，但是也让我通过了
public int firstMissingPositive(int[] nums) {
if(nums.length==0){
return 1;
}else{
Arrays.sort(nums); //排序
int result = 0;
//构建list
List<Integer> list1 = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
if(nums[i]>0){
list1.add(nums[i]);
}
}
//list去重
LinkedList<Integer> list = new LinkedList<>();
Iterator<Integer> it=list1.iterator();
while (it.hasNext()){
Integer next = it.next();
if (!list.contains(next)){
list.add(next);
}
}
if(list.size()==0){
return 1;
}else {
for (int i = 1; i <=list.size(); i++) {
if(list.get(i-1) != i){ //从1开始遍历到list的长度；然后list里面的元素也开始遍历，当不相等的时候就是缺的那个
result = i;
break;
}else {
result = i+1;
}
}
return result;
}
}
} 
京公网安备 11010502036488号