首页 > 代码库 > 求有序数组中不重复数字的出现次数

求有序数组中不重复数字的出现次数

不使用jdk的集合类,通过遍历数组得到,因为数组是有序的,在遍历数组的时候,统计整数是否重复出现,如果没有重复出现计数加一,若重复出现则是计数减一。

java解决方法,时间复杂度O(n)。

    public int countNoRepeatNum(int[] arr, int n) {
        if(arr == null || n <= 0) return -1;
        boolean repeat = false;
        int count = 1;
        int num = arr[0];
        for(int i=1;i<n;i++) {
            if(!repeat) {
                if(arr[i] != num) {
                    num = arr[i];
                    count++;
                } else {
                    repeat = true;
                    count--;
                }
            } else {
                if(arr[i] != num) {
                    count++;
                    num = arr[i];
                    repeat = false;
                } 
            }
        }
        return count;
    }

 

求有序数组中不重复数字的出现次数