7.数组（七）

https://leetcode-cn.com/tag/array/

题目汇总

219. 存在重复元素 II简单

228. 汇总区间中等

229. 求众数 II中等

238. 除自身以外数组的乘积中等

268. 缺失数字简单

219. 存在重复元素 II简单

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引i 和j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
示例 1:
输入: nums = [1,2,3,1], k= 3，输出: true
示例 2:
输入: nums = [1,0,1,1], k=1，输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k=2，输出: false

思路：哈希表，时间复杂度：O(n)

哈希表里面始终最多包含 k 个元素，当出现重复值时则说明在 k 距离内存在重复元素，每次遍历一个元素则将其加入哈希表中，如果哈希表的大小大于 k，则移除最前面的数字

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {//执行用时 :10 ms, 在所有 Java 提交中击败了80.55%的用户
        if(nums.length < 2 || k < 1)
            return false;
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            int count = 1;
            if(set.contains(nums[i])){
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

228. 汇总区间中等

给定一个无重复元素的有序整数数组，返回数组区间范围的汇总。
示例 1:
输入: [0,1,2,4,5,7]
输出: ["0->2","4->5","7"]
解释: 0,1,2 可组成一个连续的区间; 4,5 可组成一个连续的区间。
示例 2:
输入: [0,2,3,4,6,8,9]
输出: ["0","2->4","6","8->9"]
解释: 2,3,4 可组成一个连续的区间; 8,9 可组成一个连续的区间。

思路：双指针

class Solution {
    public List<String> summaryRanges(int[] nums) {//执行用时 :9 ms, 在所有 Java 提交中击败了52.07%的用户
        List<String> list = new ArrayList<>();
        int left = 0;
        int right = 0;
        for(int i=1;i<=nums.length;i++){
            if(i<nums.length&&nums[i]-1 == nums[i-1]){
                right++;
            }else{
                if(left == right){
                    list.add(nums[left] + "");
                }else{
                    list.add(nums[left] + "->" + nums[right]);
                }
                right++;
                left = right;
            } 
        }
    return list;
    }
}

229. 求众数 II中等

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明:要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
是169. 多数元素的扩展

思路：摩尔投票法

刚开始想到的是哈希表，但是不符合时间复杂度的要求
这个题解写的清清楚楚https://leetcode-cn.com/problems/majority-element-ii/solution/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/

class Solution {
    public List<Integer> majorityElement(int[] nums) {//执行用时 :2 ms, 在所有 Java 提交中击败了99.56%的用户
        // 创建返回值
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        // 初始化两个候选人candidate，和他们的计票
        int cand1 = nums[0], count1 = 0;
        int cand2 = nums[0], count2 = 0;

        // 摩尔投票法，分为两个阶段：配对阶段和计数阶段
        // 配对阶段
        for (int num : nums) {
            // 投票
            if (cand1 == num) {
                count1++;
                continue;
            }
            if (cand2 == num) {
                count2++;
                continue;
            }

            // 第1个候选人配对
            if (count1 == 0) {
                cand1 = num;
                count1++;
                continue;
            }
            // 第2个候选人配对
            if (count2 == 0) {
                cand2 = num;
                count2++;
                continue;
            }

            count1--;
            count2--;
        }

        // 计数阶段
        // 找到了两个候选人之后，需要确定票数是否满足大于 N/3
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (cand1 == num) count1++;
            else if (cand2 == num) count2++;
        }

        if (count1 > nums.length / 3) res.add(cand1);
        if (count2 > nums.length / 3) res.add(cand2);

        return res;
    }
}

238. 除自身以外数组的乘积中等

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

思路：乘积 = 当前数左边的乘积 × 当前数右边的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {//执行用时 :1 ms
        int[] res = new int[nums.length];
        int left = 1;
        int right = 1;
        for(int i=0;i<nums.length;i++){//从左到右遍历，保存它左侧所有元素的乘积
            res[i] = left;
            left *= nums[i];
        }
        for(int j=nums.length-1;j>=0;j--){//从右到左遍历，保存它右侧所有元素的乘积
            res[j] *= right;//将当前位置的左积乘以右积
            right *= nums[j];
        }
    return res;
    }
}

268. 缺失数字简单

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]，输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]，输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

思路一：排序不可取

连续的从0到n的序列，应该满足nums[i]=i

思路二：数学公式

class Solution {
    public int missingNumber(int[] nums) {执行用时 :0 ms
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
    return nums.length * (nums.length + 1) / 2 - sum;
    }
}

思路三：哈希表不可取

class Solution {
    public int missingNumber(int[] nums) {//执行用时 :9 ms
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        for(int i=0;i<nums.length;i++){
            if(!set.contains(i))
            return i;
        }
    return nums.length;
    }
}

思路四：位运算（自己没想出来）

class Solution {
    public int missingNumber(int[] nums) {//执行用时 :1 ms
        int res = nums.length;
        for(int i=0;i<nums.length;i++){
            res ^= nums[i] ^ i;
        }
    return res;
    }
}