负数计数法

Question

给定一个长度为n的数组，该数组中的每个元素在1到n范围内，要求在O(n)的时间复杂度，O(1)的空间复杂度下，打印1到n这n个数各出现了多少次。

Solution

int[] input = {3,4,1,1,1,2,2,4,3,3,3,3};
 		
int i = 0;
while (i < input.length) {
    int val = input[i];
    if (val < 0) {
        i++;
        continue;
    }
    if (val != i) {
        if (input[val] > 0) {
            swap(input, val, i);
            input[val] = -1;
            continue;
        }else {
            input[val]—;
            //计数器清0
            input[i] = 0;
            i++;
        }
    }			
}
for(i = 1; i < input.length; i++) {			
    System.out.print(input[i] * (-1) +" ");
}