1. 统计数组中元素总结1.1 统计元素出现的次数

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

  1. 如果数据的范围有限制，如：只有小写字母、1000以内的正数等，这时我们可以通过一个数组来充当map；
  2. 如果数据的范围没有限制，或者数据范围很大：如：int的数据范围，这时我们可以通过HashMap存储对应的key和value；

可参考代码：

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

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

首先想清楚一个问题：

  1. 从左到右遍历，最后遍历到的就是最右元素；
  2. 从右到左遍历，最后遍历到的就是最左元素；

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

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

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

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

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

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

  1. 对于nums中的一个数据x，我们用nums[x - 1] 来标识这个元素是否已经出现过；
  2. 为了标识nums[x - 1]是否出现过，我们不能使用nums中原来就会出现的数字，比如说：范围[1, n]之间的数字；一个常用的方法是：将nums[x - 1]转化为负数，这样就可以用来标识 x 之前是否已经出现过；
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];        }}

2. 题目记录645. 错误的集合分析题意

一个长度为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  0){                ans[1] = i + 1;                break;            }        }        return ans;    }}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

697. 数组的度分析题意

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

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

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

思路分析

由于数据的范围较大，所以我们通过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 = 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)

448. 找到所有数组中消失的数字分析题意

一个长度为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  0){                ans.add(i + 1);            }        }        return ans;    }}

复杂度分析

时间复杂度：O(n)

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

442. 数组中重复的数据分析题意

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

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

思路分析

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

  1. 如果已经存在那么它就是我们要找的重复元素，将该元素加入到结果集中；
  2. 如果不存在那么就把它加入到集合中；
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)

41. 缺失的第一个正数分析题意

给你一个未排序的整数数组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 || nums[i] <= 0){                nums[i] = nums.length + 1;            }        }        for(int i = 0; i < nums.length; i++){            int k = Math.abs(nums[i]);            if( k <= nums.length){                nums[k - 1] = - Math.abs(nums[k - 1]);            }        }        int ans = nums.length + 1;        for(int i = 0; i = 0){                ans = i+1;                break;            }        }         return ans;    }}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

本文来自博客园，作者：睡觉不打呼，转载请注明原文链接：https://www.cnblogs.com/404er/p/array_count.html