统计无序数组各元素出现的次数

题目描述

一个长度大小为N的数组，数组中的每个元素的取值范围在[1，N]，且为正整数。
问：如何在时间复杂度为O(N)，空间复杂度为O(1)的条件下，统计数组中不同元素出现的次数。

对这道题的感受

一开始接触到这道题，我是觉得不难的，因为我会开辟一个辅助数组来帮助统计这个过程。但是这道题要求的是空间复杂度为O(1)，然后这道题的难度就噌噌噌的上升，然后我现在弄明白了就来写一下我对这道题的题解吧。

解题思路

遍历数组，通过当前元素的值作为下标，找到下一个元素。最后得到的数组中，下标（因为数组的下标都是从0开始的，所以需要+1）为数组中出现的元素，每个下标对应的值取反输出即是该元素出现的次数。

若当前元素小于0，则跳过
若当前元素大于0，则判断其作为下标对应的元素是否大于0。若大于0，则把对应的元素赋值给当前元素，并把它的值设置为-1；若小于0，则把对应的元素自减1，当前元素置为0；

估计阅读到这里，你会一脸懵逼，这些当前元素和对应元素到底是什么鬼，好混。我明白，所以接下来我举个例子来讲解整个过程。

// 数组举例
int[] arr = {2, 5, 5, 2, 3};
/*
1、遍历数组，第一个arr[0]=2，然后看下标为2的元素是arr[2]=5。
2、把arr[2]对应的5赋值给arr[0]，然后arr[2]就设置为-1
3、然后重复整个过程直到结束
它的整个变化过程就是这样
- {2, 5, 5, 2, 3}
- 5, [-1], 5, 2, 3
- 3, [-1], 5, 2, [-1]
- 5, [-1], [-1], 2, [-1]
- [0], [-1], [-1], 2, [-2]
- [0], [-2], [-1], [0], [-2]
这个结果表示：1有0个，2有2个，3有一个，4有0个，5有2个
*/

代码

package Test;

/**
 * @author god-jiang
 * @date 2020/1/22  17:30
 */
public class CountArr {
    public static void work(int[] arr, int n) {
        int index = 0;
        while (index < n) {
            //因为数组都是从0开始的，所以arr[index]得减1才可以找到对应的元素，否则会数组越界
            int temp = arr[index] - 1;
            if (temp < 0) {
                index++;
                continue;
            }
            if (arr[temp] > 0) {
                arr[index] = arr[temp];
                arr[temp] = -1;
            } else {
                arr[temp]--;
                arr[index] = 0;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 5, 2, 3};
        work(arr, arr.length);
        int index = 1;
        for (int countResult : arr
        ) {
            System.out.println(index++ + "出现了" + (-1) * countResult + "次");
        }
    }
}