上次面试字节，碰到一个比较有意思的算法题，记录一下，给各位牛友分享。
题意：
给定一个无序数组，长度为n，每个元素都属于范围[1,n]之间，使用时间复杂度O(n)+空间复杂度O(1)的方法，求得每个元素的出现次数。
比如给定数组[1,2,2,3,5,3]，最后的结果就是类似于1:1,2:2,3:2,5:1的形式，表示1出现了1次，2出现了2次，3出现了2次，5出现了1次。

解法：
这里限定了时间复杂度，那么只能用边遍历边替换的思路，力扣有移到类似的题 缺失的第一个正数，可以移步查看。

思想就是遍历数组，通过当前位置的数找到对应的下标位置，如果为正数，说明还没有被访问到，需要交换并置为-1，若为负数，需要减去1，若找到的下标不为自己，则把当前位置设为0，之后继续遍历。

步骤：

       1,2,2,3,5,3
第一步 -1,2,2,3,5,3
第二步 -1,-1,2,3,5,3
第三步 -1,-2,0,3,5,3
第四步 -1,-2,-1,0,5,3
第五步 -1,-2,-1,0,-1,3
第六步 -1,-2,-2,0,-1,0

代码：

public class Main {
    public static void main(String[] args) {
        int[][] nums = {
                {1, 1, 2, 2, 3, 5, 2, 3},
                {2, 3, 2, 3, 1},
                {5, 4, 3, 2, 1}
        };
        for (int[] num : nums) {
            System.out.println(Arrays.toString(count(num)));
        }
        // [-2, -3, -2, 0, -1, 0, 0, 0]
        // [-1, -2, -2, 0, 0]
        // [-1, -1, -1, -1, -1]
    }

    public static int[] count(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            // 只考虑大于0的元素
            while (nums[i] > 0) {
                // 下一个位置
                int next = nums[i] - 1;
                if (nums[next] > 0) {
                    // 交换元素
                    nums[i] = nums[next];
                    nums[next] = -1;
                } else {
                    nums[i] = 0;
                    nums[next]--;
                }
            }
            ++i;
        }
        return nums;
    }
}