数组的遍历、统计数组中的元素——LeetCode

一、数组的遍历

1、最大连续1的个数（简单）

自己的想法

方法一：遍历数组，计算每个区间 1 的个数，求出最大的即可。

• 执行用时：2 ms, 在所有 Java 提交中击败了94.09%的用户
• 内存消耗：40.3 MB, 在所有 Java 提交中击败了68.99%的用户

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;
        int tmp = 0;
        for (int i : nums) {
            if (i == 1) {
                tmp++;
            } else {
                max = Math.max(max, tmp);
                tmp = 0;
            }
        }
        return Math.max(max, tmp);
    }
}

看题解后

方法二：通过每一段 1 的起始和结束下标，计算 1 的个数。

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：40.3 MB, 在所有 Java 提交中击败了63.84%的用户

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;
        int right = 0;
        int max = 0;
        for (; right < nums.length; right++) {
            if (nums[right] == 0) {
                max = Math.max(max, right - left);
                left = right + 1;
            }
        }
        return Math.max(max, right - left);
    }
}

2、提莫攻击（中等）

自己的想法

方法一：每次中毒后，直接加上当前中毒的时间；下次中毒后，判断上次中毒是否结束，从而进行相应的累加。

• 执行用时：2 ms, 在所有 Java 提交中击败了98.73%的用户
• 内存消耗：40.2 MB, 在所有 Java 提交中击败了90.08%的用户

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        // 中毒时间
        int a = 0;
        // 当前的中毒结束时间
        int b = 0;
        for (int i : timeSeries) {
            if (i >= b) {
                // 如果之前的中毒已经结束，则直接累加
                a += duration;
            } else {
                // 如果直接的中毒未结束，则只累加续上的时间
                a += duration - (b - i);
            }
            // 计算当前中毒的结束时间
            b = i + duration;
        }
        return a;
    }
}

看题解后

方法二：使用下次中毒的起始时间减去当前中毒起始时间得到 x，如果 x < 中毒持续时间，则表示上一次中毒没结束下次中毒就开始了，所以只需要累加上 x 即可；最后需要再加一个最后一次中毒的中毒持续时间。

• 执行用时：2 ms, 在所有 Java 提交中击败了98.73%的用户
• 内存消耗：39.9 MB, 在所有 Java 提交中击败了96.55%的用户

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int n = timeSeries.length;
        // 如果没有攻击直接结束
        if (n == 0) return 0;
        int total = 0;
        for(int i = 0; i < n - 1; i++)
          // 每次只加最短的持续时间
          total += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
        return total + duration;
    }
}

3、第三大的数（简单）

自己的想法

方法一：遍历数组依次求第一、第二、第三大的值，用 Integer.MIN_VALUE - 1 表示当前数有没有被赋值，最后判断 a3 有没有被赋值，从而返回相应的值。（这道题我竟然写了一个小时，掉类型转换的坑里了）

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.4 MB, 在所有 Java 提交中击败了62.66%的用户

class Solution {
    public int thirdMax(int[] nums) {
        long a1 = (long) Integer.MIN_VALUE - 1;
        long a2 = (long) Integer.MIN_VALUE - 1;
        long a3 = (long) Integer.MIN_VALUE - 1;
        for (int num : nums) {
            if (num > a3 && num != a2 && num != a1) {
                    if (num > a2) {
                        if (num > a1) {
                            a3 = a2;
                            a2 = a1;
                            a1 = num;
                        } else {
                            a3 = a2;
                            a2 = num;
                        }
                    } else {
                        a3 = num;
                    }
                }
            }
        // 如果a3没变，则返回a1
        return (int) (a3 != (long) Integer.MIN_VALUE - 1 ? a3 : a1);
    }
}

看题解后

方法二：内存优化，不使用 long。该方法和上个方法的区别在于，它用一个变量记录 Integer.MIN_VALUE 有没有出现，从而判断 a3 有没有被赋值。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.2 MB, 在所有 Java 提交中击败了85.76%的用户

class Solution {
    public int thirdMax(int[] nums) {
        int a1, a2, a3;
        boolean containMin = false;
        a1 = a2 = a3 = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num == Integer.MIN_VALUE) {
                containMin = true;
            }
            if (num > a3 && num != a2) {
                if (num != a1) {
                    if (num > a2) {
                        if (num > a1) {
                            a3 = a2;
                            a2 = a1;
                            a1 = num;
                        } else {
                            a3 = a2;
                            a2 = num;
                        }
                    } else {
                        a3 = num;
                    }
                }
            }
        }
        if (containMin) {
            // 最小值出现，且 t2 == t3 ，则表示：第三大的值没有出现
            return a2 == a3 ? a1 : a3;
        } else {
            // 最小值没出现，如果 t3 还未初值，则表示：第三大的值没有出现
            return a3 == Integer.MIN_VALUE ? a1 : a3;
        }
    }
}

4、三个数的最大乘积（简单）

自己的想法

方法一：因为数组中有负数，所以需要求出三个最大的数和两个最小的数（一次遍历），然后求出三个数最大的乘积。

• 执行用时：2 ms, 在所有 Java 提交中击败了99.50%的用户
• 内存消耗：39.7 MB, 在所有 Java 提交中击败了88.08%的用户

class Solution {
    public int maximumProduct(int[] nums) {
        // 求出三个最大
        int a1, a2, a3;
        a1 = a2 = a3 = -1001;
        // 求出二个最小
        int b1, b2;
        b1 = b2 = 1001;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < b2) {
                if (nums[i] < b1) {
                    b2 = b1;
                    b1 = nums[i];
                } else {
                    b2 = nums[i];
                }
            }
            if (nums[i] > a3) {
                if (nums[i] > a2) {
                    if (nums[i] > a1) {
                        a3 = a2;
                        a2 = a1;
                        a1 = nums[i];
                    } else {
                        a3 = a2;
                        a2 = nums[i];
                    }
                } else {
                    a3 = nums[i];
                }
            }
        }
        return Math.max(a1 * a2 * a3, a1 * b1 * b2);
    }
}

方法二：利用排序得出三个最大的数和两个最小的数。

• 执行用时：12 ms, 在所有 Java 提交中击败了69.41%的用户
• 内存消耗：39.9 MB, 在所有 Java 提交中击败了71.20%的用户

public class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        return Math.max(nums[0] * nums[1] * nums[nums.length - 1], nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3]);
    }
}

5、早餐组合（简单）

自己的想法

方法一：排序+二分查找

• 执行用时：160 ms, 在所有 Java 提交中击败了5.47%的用户
• 内存消耗：58.2 MB, 在所有 Java 提交中击败了35.40%的用户

class Solution {
    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        Arrays.sort(drinks);
        int sum = 0;
        for (int i : staple) {
            sum = (sum + getRight(drinks,x - i)) % 1000000007;
        }
        return sum;
    }

    private int getRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 注意这样写，可以从右边收缩待搜索区间的范围，进而找到最后一次出现的位置
            if (nums[mid] > target) {
                // mid 以及 mid 右边都不是，下一轮搜索区间在 [left, mid - 1]
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        // 需要对 0 特殊处理
        if (left == 0 && nums[0] > target) {
            return 0;
        }
        return left + 1;
    }
}

看题解后

方法二：排序+双指针

• 执行用时：88 ms, 在所有 Java 提交中击败了37.46%的用户
• 内存消耗：57.9 MB, 在所有 Java 提交中击败了77.24%的用户

class Solution {
    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        Arrays.sort(staple);
        Arrays.sort(drinks);
        int sum = 0, left = 0, right = drinks.length - 1;
        while (left < staple.length && right >= 0) {
            // 如果钱不够，则减少饮料的价格
            if (staple[left] + drinks[right] > x) {
                right--;
            } else {
                // 计算当前主食可以匹配的饮料个数
                sum = (sum + right + 1) % 1000000007;
                // 换下一种主食
                left++;
            }
        }
        return sum;
    }
}

方法三：计数排序+前缀和

• 执行用时：6 ms, 在所有 Java 提交中击败了97.58%的用户
• 内存消耗：48.8 MB, 在所有 Java 提交中击败了92.47%的用户

class Solution {
    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        int count = 0;
        // 对 staple 进行计数排序
        int[] array = new int[x + 1];
        for (int i : staple) {
            if (i <= x) {
                array[i]++;
            }
        }
        // 计算前缀和，得到 staple 中价格低于等于 i 的方案数量
        for (int i = 1; i < x + 1; i++) {
            array[i] += array[i - 1];
        }
        // 根据前缀和，返回 array 中价格低于等于 x-i 可行的方案数量
        for (int i : drinks) {
            if (i <= x) {
                count += array[x - i];
                //减少取余次数小技巧
                if (count >= 1000000007) {
                    count -= 1000000007;
                }
                // count %= 1000000007;
            }
        }
        return count;
    }
}

6、采购方案（简单）

自己的想法

方法一：排序+二分查找

• 执行用时：110 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：48 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int purchasePlans(int[] nums, int target) {
        Arrays.sort(nums);
        long count = 0;
        for (int i = 0; i < nums.length; i++) {
            int index = getRight(nums, i, target - nums[i]);
            count += (index - i);
        }
        return (int) (count % 1000000007);
    }

    private int getRight(int[] nums, int i, int target) {
        int left = i, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 注意这样写，可以从右边收缩待搜索区间的范围，进而找到最后一次出现的位置
            if (nums[mid] > target) {
                // mid 以及 mid 右边都不是，下一轮搜索区间在 [left, mid - 1]
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

方法二：排序+双指针

• 执行用时：38 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：48 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int purchasePlans(int[] nums, int target) {
        int mod = 1_000_000_007;
        int result = 0;
        // 排序
        Arrays.sort(nums);
        // 双指针，left 从前往后找，right 从后往前
        int left = 0, right = nums.length - 1;
        while (left < right) {
            // 如果当前左右之和大于了目标值，说明偏大了，就把右指针往左移动
            if (nums[left] + nums[right] > target) {
                right--;
            } else {
                // 否则的话，说明找到了合适的，需要把两者中间的元素个数都累加起来
                result += right - left;
                result %= mod;
                // 然后再向右移动左指针
                left++;
            }
        }
        return result;
    }
}

方法三：计数排序+前缀和

• 执行用时：9 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：48.3 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int purchasePlans(int[] nums, int target) {
        int[] price = new int[target];
        // 计数排序
        for (int i : nums) {
            if (i < target) {
                price[i]++;
            }
        }
        // 前缀和
        for (int i = 1; i < target; i++) {
            price[i] += price[i - 1];
        }
        long count = 0;
        for (int i : nums) {
            if (i < target) {
                count += price[target - i];
                // 排除统计到自身的情况
                if (2 * i <= target) {
                    count--;
                }
            }
        }
        // 排除元素之间重复统计的数量
        return (int) (count / 2 % 1000000007);
    }
}

二、统计数组中的元素

1、错误的集合（简单）

自己的想法

方法一：计数排序

  使用计数排序的思想，创建一个等长的数组，用来记录原数组中的所有数出现的次数。

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：40.4 MB, 在所有 Java 提交中击败了25.71%的用户

public class Solution {
    public int[] findErrorNums(int[] nums) {
        // 0 存储重复出现的数，1 存储丢失的数
        int[] result = new int[2];
        int[] array = new int[nums.length + 1];
        for (int i : nums) {
            // 如果不为 0，则表示该数已经出现过，进行记录
            if (array[i] != 0) {
                result[0] = i;
            }
            array[i] = 1;
        }
        for (int i = 1; i < array.length; i++) {
            // 如果为 0 则表示该数没有出现过，进行记录
            if (array[i] == 0) {
                result[1] = i;
                break;
            }
        }
        return result;
    }
}

看题解后

方法二：原地修改（方法一的空间优化）

  方法一创建了新的数组，如果我们可以在原数组上对值进行标记，就可以不使用额外空间。我们用 nums[nums[i]-1] 来判断 nums[i] 是否出现过（减1是为了防止下标越界，数组下标从0开始，而数值从1开始），如果 nums[i] 第一次出现则将 nums[nums[i]-1] * -1，使用这样的方法就可以实现在原数组上对值进行标记。（注意下标越界的问题）

• 执行用时：3 ms, 在所有 Java 提交中击败了70.43%的用户
• 内存消耗：40.1 MB, 在所有 Java 提交中击败了48.54%的用户

public class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            // 数组中的数可能是负数，需要其绝对值
            int tmp = Math.abs(nums[i]) - 1;
            if (nums[tmp] < 0) {
                result[0] = tmp + 1;
            } else {
                nums[tmp] = -nums[tmp];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                result[1] = i + 1;
                break;
            }
        }
        return result;
    }
}

方法三：位运算

  首先需要知道一个概念，一个数和它本身进行异或运算结果为 0；对数组中的所有数和 1~nums.length 的数进行异或运算，就能得到丢失的数和重复的数的异或结果（xor）；然后求 xor 的最右比特位，(1001 0100) 的最右比特位就是 (0000 0100)，使用公式 int right = xor & (xor ^ (xor - 1)) 即可。

  因为 xor 是丢失的数和重复的数的异或结果，而异或运算是不同位为 1 相同位为 0，所以根据最右比特位可以将数组中的数和 1~nums.length 的数划分为两类，分别进行异或运算即可得到丢失的数和重复的数。最后再遍历原数组判断哪个是重复的数哪个是丢失的数即可。

• 执行用时：2 ms, 在所有 Java 提交中击败了92.45%的用户
• 内存消耗：40.1 MB, 在所有 Java 提交中击败了50.02%的用户

public class Solution {
    public int[] findErrorNums(int[] nums) {
        // 首先将数组中的所有数和1~nums.length的数进行异或运算
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= i;
            xor ^= nums[i];
        }
        // 补上最后一个数，得到的 xor 是丢失的数和重复的数的异或结果
        xor ^= nums.length;
        int a = 0;
        int b = 0;
        // 求 xor 的最右比特位
        int right = xor & (xor ^ (xor - 1));
        // 求最右比特位的作用：异或运算是不同为 1 相同为 0，
        // 所以根据该比特位即可区分丢失的数和重复的数，分别进行异或运算即可得到丢失的数和重复的数
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & right) == 0) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
            if ((i & right) == 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        // 补上最后一个数
        if ((nums.length & right) == 0) {
            a ^= nums.length;
        } else {
            b ^= nums.length;
        }
        for (int i : nums) {
            // 如果存在则 a 为重复的数
            if (i == a) {
                return new int[]{a, b};
            }
        }
        return new int[]{b, a};
    }
}

其他方法：使用排序和 Map 的方法比较简单就不再进行编码了。

2、数组的度（简单）

自己的想法

方法一：自定义数据结构

  题目要求找到相同大小的度的最短连续子数组，也是查找一个出现次数最多且所在的子数组最短。所在子数组最短，我们可以使用（该数出现的起始下标-该数出现的结束下标+1）得到。所以我们可以定义一个数据结构，来存储每个数出现的次数以及起始和结束下标。
  定义一个 HashMap 集合，key 表示数组中指定的值，value 为自定义的数据结构。然后遍历数组将每个数添加到集合中。最后找到出现次数最多且（起始下标-结束下标）最小的值，起始下标-结束下标+1 就是最终答案。

• 执行用时：17 ms, 在所有 Java 提交中击败了88.76%的用户
• 内存消耗：42.8 MB, 在所有 Java 提交中击败了38.15%的用户

class Solution {
    public int findShortestSubArray(int[] nums) {
        // 键表示指定值
        Map<Integer, Degree> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 存在则加次数更新结束下标，否则则添加
            if (map.containsKey(nums[i])) {
                Degree d = map.get(nums[i]);
                d.end = i;
                d.count++;
                map.put(nums[i], d);
            } else {
                map.put(nums[i], new Degree(1, i, i));
            }
        }
        Degree tmp = Collections.max(map.values());
        return tmp.end - tmp.start + 1;
    }

    private class Degree implements Comparable {
        // 当前数出现的次数
        int count;
        // 起始下标和结束下标
        int start;
        int end;

        public Degree(int count, int start, int end) {
            this.count = count;
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Object o) {
            Degree tmp = (Degree) o;
            if (count == tmp.count) {
                // 如果度相同，end-start 越小越大
                //return (tmp.end-tmp.start) - (end-start) ;
                return tmp.end - tmp.start - end + start;
            }
            return count - tmp.count;
        }
    }
}

看题解后

方法二：计数排序

  题目上说数据范围为 [0 ~ 49,999] 的整数，所以可以使用计数排序的思想，将每个出现的数记录在指定 count 数组中。在初始化 count 数组时，可以顺便统计一下数组的度。如果数组的度为 1，则结果必为 1，直接返回 1 即可。如果数组度不为 1，则遍历 count 数组，如果数组的度和 count 数组中记录值相同，则表示该数可能为结果，查找该数在原数组的起始和结束下标，求出其子数组的长度。由于该数可能为多个，则求出最短子数组返回即可。

• 执行用时：5 ms, 在所有 Java 提交中击败了98.69%的用户
• 内存消耗：40.1 MB, 在所有 Java 提交中击败了99.11%的用户

class Solution {
    public int findShortestSubArray(int[] nums) {
        // 使用计数排序的思想
        int[] count = new int[50000];
        // 记录出现最高的次数是多少次数
        int degree = 0;
        for (int i : nums) {
            degree = Math.max(degree, ++count[i]);
        }
        // 如果数组的度为 1，则结果必为 1
        if (degree == 1) {
            return 1;
        }
        int result = nums.length;
        for (int i = 0; i < count.length; i++) {
            if (degree != count[i]) {
                continue;
            }
            // 求该数出现的起始和结束的下标
            int start = 0, end = nums.length - 1;
            while (start < end && i != nums[start]) {
                start++;
            }
            while (start < end && i != nums[end]) {
                end--;
            }
            result = Math.min(result, end - start + 1);
        }
        return result;
    }
}

方法三：计数排序（优化）

  在方法二中直接根据题目的数据，定义一个长度为 50,000 的数组，其实数组中的所有数并没有都利用。可以通过查找数组中的最大值和最小值，从而定义一个长度为 Max-Min+1 的数组。其它的思路不变...

• 执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：43.5 MB, 在所有 Java 提交中击败了19.20%的用户

class Solution {
    public int findShortestSubArray(int[] nums) {
        // 找到数组中的最小数和最大数
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i : nums) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        // 使用计数排序的思想
        int[] count = new int[max - min + 1];
        // 记录出现最高的次数是多少次数
        int degree = 0;
        for (int i : nums) {
            degree = Math.max(degree, ++count[i - min]);
        }
        // 如果数组的度为 1，则结果必为 1
        if (degree == 1) {
            return 1;
        }
        int result = nums.length;
        for (int i = 0; i < count.length; i++) {
            if (degree != count[i]) {
                continue;
            }
            // 还原原数的值
            int tmp = min + i;
            // 求该数出现的起始和结束的下标
            int start = 0, end = nums.length - 1;
            while (start < end && tmp != nums[start]) {
                start++;
            }
            while (start < end && tmp != nums[end]) {
                end--;
            }
            result = Math.min(result, end - start + 1);
        }
        return result;
    }
}

3、找到所有数组中消失的数字（简单）

自己的想法

方法一：原地修改

  不使用额外空间，在原数组上对值进行标记。我们用 nums[nums[i]-1] 来判断 nums[i] 是否出现过（减1是为了防止下标越界，数组下标从0开始，而数值从1开始），如果 nums[i] 第一次出现则将 nums[nums[i]-1] * -1，使用这样的方法就可以实现在原数组上对值进行标记。（注意下标越界的问题）

• 执行用时：6 ms, 在所有 Java 提交中击败了89.18%的用户
• 内存消耗：47.5 MB, 在所有 Java 提交中击败了45.44%的用户

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int tmp = Math.abs(nums[i]) - 1;
            if (nums[tmp] > 0) {
                nums[tmp] = -nums[tmp];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                list.add(i + 1);
            }
        }
        return list;
    }
}

方法二：计数排序

  使用计数排序的思想进行求解。违背题意，使用了额外存储空间，但是满足了我追求 100% 的强迫症。

• 执行用时：3 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：47.6 MB, 在所有 Java 提交中击败了35.13%的用户

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        boolean[] exist = new boolean[nums.length + 1];
        for (int i : nums) {
            exist[i] = true;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {
            if (!exist[i]) {
                list.add(i);
            }
        }
        return list;
    }
}

4、数组中重复的数据（中等）

自己的想法

方法一：原地修改

  不使用额外空间，在原数组上对值进行标记。我们用 nums[nums[i]-1] 来判断 nums[i] 是否出现过（减1是为了防止下标越界，数组下标从0开始，而数值从1开始），如果 nums[i] 第一次出现则将 nums[nums[i]-1] * -1，使用这样的方法就可以实现在原数组上对值进行标记。（注意下标越界的问题）

• 执行用时：6 ms, 在所有 Java 提交中击败了92.28%的用户
• 内存消耗：47.3 MB, 在所有 Java 提交中击败了76.31%的用户

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int tmp = Math.abs(nums[i]) - 1;
            // 如果 nums[tmp] < 0 则表示该数已出现过进行记录
            if (nums[tmp] > 0) {
                nums[tmp] = -nums[tmp];
            } else {
                list.add(tmp + 1);
            }
        }
        return list;
    }
}

方法二：计数排序

  使用计数排序的思想进行求解，创建一个新的数组来记录数组中的值出现的次数。违背题意，使用了额外存储空间，但是满足了我追求 100% 的强迫症。

• 执行用时：4 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：47.3 MB, 在所有 Java 提交中击败了76.65%的用户

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int[] count = new int[nums.length + 1];
        for (int i : nums) {
            count[i]++;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {
            if (count[i] == 2) {
                list.add(i);
            }
        }
        return list;
    }
}

5、缺失的第一个正数（困难）

看题解后

方法一：原地修改

  数组长度为 n，所以未出现的最小正整数，最小值是 1 最大值是 n+1。题目说只能使用常数级别的额外空间，所以不能使用计数排序的方法，使用原地修改的方法（两种方法如何应用可以参考上面的题）。但使用原地修改的方法，需要将数组中的数转为负数，从而判断当前下标的数是否出现过。而数组中有负数和零，显然这已经影响到我们的判断，所以我们需要先对数组中的数做预处理，将 <=0 的数改为 n+1（因为题解的最大值 n+1 所以这并不影响题解）。接着使用原地修改的方法进行操作即可，注意：不需要对 < 0 和 > n 进行操作。

• 执行用时：1 ms, 在所有 Java 提交中击败了79.13%的用户
• 内存消耗：36 MB, 在所有 Java 提交中击败了91.48%的用户

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = nums.length + 1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            int tmp = Math.abs(nums[i]) - 1;
            if (tmp < nums.length && nums[tmp] > 0) {
                nums[tmp] = -nums[tmp];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

方法二：置换

  数组长度为 n，所以未出现的最小正整数，最小值是 1 最大值是 n+1。所以对于一个 0 < nums[i] <= n 的数，我们可以将它移动到它应在的下标 nums[i]-1。进行这样的移动后原数组：[3, 4, -1, 1, 10]，移动后为：[1, -1, 3, 4, 10]，再次遍历数组就可以查找到缺失的数。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.3 MB, 在所有 Java 提交中击败了59.04%的用户

class Solution {
    public static int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 将当前数交换到它应在的位置。如果当前数已在它应在的位置，则不进行交换 nums[nums[i] - 1] != nums[i]
            while (nums[i] > 0 && nums[i] <= nums.length && 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 < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

6、H 指数（中等）

自己的想法

方法一：排序

  这各题用大白话说就是，求一个最大数 n，满足至少有 n 个数大于等于 n。所以我们可以对数组进行升序排序，然后逆序查找最大数 n 即可。

• 执行用时：1 ms, 在所有 Java 提交中击败了84.47%的用户
• 内存消耗：36.1 MB, 在所有 Java 提交中击败了92.40%的用户

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int result = 0;
        for (int i = citations.length - 1; i >= 0; i--) {
            // 因为数组是升序排序，倒序遍历。如果当前数已经小于或等于 n 值，则后面的数肯定不满足条件。
            if (citations[i] <= result) {
                return result;
            }
            result++;
        }
        return result;
    }
}

看题解后

方法二：计数排序

  该题的最大解为 citations.length，所以大于 citations.length 的值都可以视为 citations.length。创建新的数组，对原数组进行计数排序。然后对新数组进行逆序查找满足条件的 n 即可。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.2 MB, 在所有 Java 提交中击败了83.99%的用户

class Solution {
    public int hIndex(int[] citations) {
        int[] array = new int[citations.length + 1];
        for (int i : citations) {
            if (i > citations.length) {
                array[citations.length]++;
            } else {
                array[i]++;
            }
        }
        int count = 0;
        int i = citations.length;
        while (i > 0) {
            // 统计 >=i 数的个数
            count += array[i];
            // 如果有 count 个 >=i 的数，则直接返回
            if (i <= count) {
                return i;
            }
            i--;
        }
        return i;
    }
}

  代码简化：

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] papers = new int[n + 1];
        // 计数
        for (int c : citations){
            papers[Math.min(n, c)]++;
        }
        // 找出最大的 i
        int i = n;
        for (int count = papers[n]; i > count; count += papers[i]){
            i--;
        }
        return i;
    }
}