统计数组中各个元素出现的次数，元素取值范围为：1到N

问题描述：

* 给定一个整数数组a，长度为N，元素取值范围为[1,N]。

* 统计各个元素出现的次数，要求时间复杂度为O(N)，空间复杂度为O(1)。

* 可以改变原来数组结构。

思路：

* 从第一个元素开始遍历，每遍历到一个元素，将（该元素值 - 1 记为index）作为一个下标值，令该下标对应的元素值为元素 index+1出现的次数。

* 若下标index为负值，说明该元素已经处理过，跳过；

* 判断，若a[index]为正，则赋初值-1；若为负，则执行减1操作。

* 最后，数组中存储的元素即为统计次数，而该元素对应的下标+1即为元素值。

代码：

public static void main(String[] args) {

        // TODO Auto-generated method stub

        int n = 6;

        int[] a = new int[]{6,2,4,1,2,5};

        int i = 0;

        //采用while循环

        while(i < n){

            //由于元素取值范围为[1,N]，因此，可以将（当前元素值-1）作为下标值，找到相应位置处的元素，将其存储的值作为-times，因为原来存储值都为正值，为防止混淆，用负值存储

            int temp = a[i] - 1;

            if(temp < 0){ //表示该元素已经处理过了，跳过

                i++;

                continue;

            } else if(a[temp] > 0){//第一次处理一个值

                a[i] = a[temp];//暂存新元素

                a[temp] = -1;

            } else {//已经不是第一次处理该值了

                a[i] = 0; //没有新的元素要处理，置0

                a[temp]--;

            }

        }

        for(int j = 0; j < n; ++j){

            System.out.print(j+1 + " , " + -a[j] + "\t");

        }

    }

巴特西

统计数组中各个元素出现的次数，元素取值范围为：1到N

最新文章

热门文章