统计数组中的元素

1.1 统计元素出现的次数

为了统计元素出现的次数，我们肯定需要一个 map来记录每个数组以及对应数字出现的频次。这里 map的选择比较有讲究：

可参考代码：

for(int i = 0; i< nums.length; i++){
        count[nums[i]]++;
}

1.2 ⭐统计元素在数组中出现的最左和最右位置

首先想清楚一个问题：

我们就可以依据此，创建 left和 right变量，从左往右遍历时更新 right，从右往左遍历时更新 left。

for(int i = 0; i < nums.length; i++){
        if(nums[i] == target){
                right = i;
        }
}

for(int i = nums.length - 1; i >= 0; i--){
     if(nums[i] == target){
                left = i;
     }
}

1.3 ⭐统计元素有没有出现(有没有重复出现)

思路仍然是：统计元素出现的次数，最后根据 count数组来判断元素是否出现或者元素是否重复出现。

有时，题目要求我们空间复杂度为O(1)，这时我们要仔细地审题。 挖掘统计数组与原数组之间的关系，一般情况下我们只能通过修改原数组来统计每个元素出现的次数。比如说：如果数组中元素都在 [1, n]之间，而且原数组的长度也为： n，此时我们就可以通过修改原数组来记录元素出现的次数。

在这种类型的题目中，一个有用的观念是：

for(int i = 0; i < nums.length; i++){
        // 防止 x 为负数
        int x = Math.abs(nums[i));

        if(nums[x - 1] < 0){
            // 出现过，做操作
        }else{
            // 通过负数来标识元素x已经出现过了
            nums[x - 1] = - nums[x - 1];
        }
}

一个长度为 n的集合 s中本来存储的是 1-n的数据，将数据打乱后并挑选一个数据替换成 1-n之间的其他数据。请你找出：被替换的数据和替换成的数据。

这道题的关键在于：数据其实是无序的，所以我们不能依靠相邻元素的大小关系来进行判断。

如果我们能够统计数组中每个元素的出现次数，那么查到被替换的数据（频次为0），替换成的数据（频次为2）就十分的简单。

int[] count = new int[nums.length];
for(int i = 0; i < nums.length; i++){
        count[nums[i] - 1] ++;
}

for(int i = 0; i < count.length; i++){

        if(count[i] == 0){
        // 被替换的元素
        }

        if(count[i] == 2){
        // 替换的元素
        }
}

我们可以发现， count的大小为 n，而 nums的大小也为 n。那么我们能不能用 nums数组来标识一个元素是否出现过呢？答案是可以的。

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] ans = new int[2];
        for(int i = 0; i < nums.length; i++){
            int k = Math.abs(nums[i]);
            if(nums[k - 1] < 0){
                // 前面已经出现过
                ans[0] = k;
            }else{
                nums[k - 1] = - nums[k - 1];
            }
        }
        // 经过上述过程
        // 如果x出现，那么nums[x - 1] 为负数
        // 如果x没有出现，那么nums[x - 1]保持原样不变
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                ans[1] = i + 1;
                break;
            }
        }

        return ans;
    }
}

时间复杂度： O(n)

空间复杂度： O(1)

要想知道元素 从出现的最大频次，那么我们需要统计每个元素出现的次数。

要计算长度就需要知道最大出现元素的起始位置和终止位置，即元素的最左位置和最右位置。

所以，这道题就转化为了：求每个元素频次以及最左和最右位置。

由于数据的范围较大，所以我们通过 map来进行存储。

class Solution {
    public int findShortestSubArray(int[] nums) {
        HashMap count = new HashMap<>();
        HashMap left = new HashMap<>();
        HashMap right = new HashMap<>();

                // 统计频次和最右元素
        for(int i = 0; i < nums.length; i++){
            count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
            right.put(nums[i], i);
        }
                // 统计最左元素
        for(int i = nums.length - 1; i >= 0; i--){
            left.put(nums[i], i);
        }

        int maxFreq = 0;
        int minLen = 0;
        for(Map.Entry entry: count.entrySet()){
            if(entry.getValue() > maxFreq){
                maxFreq = entry.getValue();
                minLen = right.get(entry.getKey()) - left.get(entry.getKey()) + 1;
            }else if(entry.getValue() == maxFreq){
                minLen = Math.min(minLen, right.get(entry.getKey()) - left.get(entry.getKey()) + 1);
            }
        }

        return minLen;

    }
}

时间复杂度： O(n)

空间复杂度： O(n)

一个长度为 n的数组内，所有数字都在 1-n范围内。请找出在 1-n范围内但是没有出现在数组中的元素。

如果我们知道 1-n范围内每个数字出现的频次，那么出现频次为 0的所有元素都是我们想要找的元素。进一步来说，其实我们只关注这个元素是否出现过，即： >0 和 =0的差别，不关心具体出现了几次。

题目要求我们使用常数空间复杂度来解决这道题目。那我们只能通过修改原数组来实现统计是否元素是否出现这个需求。和上面一样，我们使用 nums[x - 1]是否为负数来标识元素 x是否已经出现过。

class Solution {
    public List findDisappearedNumbers(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            int k = Math.abs(nums[i]);
            // 确保将 k-1 置为负数
            nums[k - 1] = - Math.abs(nums[k - 1]);
        }

        List ans = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                ans.add(i + 1);
            }
        }

        return ans;

    }
}

时间复杂度： O(n)

空间复杂度： O(1), 返回元素不计算

长度为 n的数组中，每个元素都在 1-n范围内，且每个元素要么出现 1次，要么出现 2次，（其实隐含着： 1-n内的有些元素并不在数组中，因为存在重复元素）找出所有出现 2次的元素。

要求：时间复杂为 O(n)，空间复杂度为 O(1)

如果我们能用一个集合存储已经出现过的元素，然后每次遍历一个新元素时先判断该元素是否在已有的集合中：

for(int i = 0; i < nums.length; i++){
        // 如果set中没有该元素，添加成功返回true
        // 如果set中存在该元素，添加失败返回false
        if(!set.add(nums[i]){
                ans.add(nums[i]);
        }

}

上述方法的时间复杂度为 O(n)，但是空间复杂度也是 O(n)，不符合要求。那么 我们是否有办法降低时间复杂度呢？

由于数组的长度是 n，数组中每一个数字都在 1-n范围内，所以我们可以用 nums[x - 1] 来标识元素 x 的状态：是否已经出现过，这样我们就可以实现 O(1)空间复杂度了。

class Solution {
    public List findDuplicates(int[] nums) {
        List ans = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            int k = Math.abs(nums[i]);
            if(nums[k - 1] < 0){
                // 已经出现过，这一次是第二次出现
                ans.add(k);
            }else{
                nums[k - 1] = - nums[k - 1];
            }

        }

        return ans;
    }
}

时间复杂度： O(n)

空间复杂度： O(1)

给你一个未排序的整数数组 nums ，请你找出其中 没有出现的最小的正整数。

请你实现时间复杂度为 O(n)并且只使用常数级别额外空间的解决方案。

对于一个长度为 n的数组，其中没有出现的最小正整数的范围一定在： 1~(n+1)范围内。所以我们关注的数据只有 1~(n+1)中每个数的出现频次。

题意中我们已经明白了：统计 1~(n+1)中每个元素的出现频次，其实我们只统计 1~n就可以了。如果 1~n都出现了，那么最小的正整数就是 n+1。

统计 1~n每个元素出现频次，那么我们需要一个长度为 n的数组，这样的话空间复杂度就是 O(n)，不符合题意。那我们就只能从修改原数组下手了。

还记得之前的题目，我们都是通过 nums[x - 1]来标识元素 x是否出现过，这道题依旧适用，但是要做一点点修改。因为我们需要用负数标识元素已经出现过，但是原数组中的数据的范围是 ([-2^{(31)}, 2^{31}-1])存在负数，所以我们需要先将超出 1~n范围内的数组全部置为 n+1 。

class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > nums.length || nums[i] = 0){
                ans = i+1;
                break;
            }
        }

         return ans;
    }
}

时间复杂度： O(n)

空间复杂度： O(1)

Original: https://www.cnblogs.com/404er/p/array_count.html
Author: 睡觉不打呼
Title: 统计数组中的元素