給定一個有序數(shù)組，數(shù)組中有正數(shù)、負數(shù)或者0，對數(shù)組中所有的數(shù)求平方后問有多少個不同的值。
比如對于數(shù)組[-1,0,1,1,1,1]，對數(shù)組求平方后為[1,0,1,1,1,1]，那么最終的結果是2，因為最后只有0和1兩個不同的數(shù)；

對于數(shù)組[-1,0,1,2,3]，對數(shù)組求平方后為[1,0,1,4,9]，那么最終的結果是4，因為最后數(shù)組中為0,1,4,9這四個不同的數(shù)；

同事提到只有時間復雜度為O(n)，空間復雜度為O(1)的算法

  /*
     * 有序數(shù)據(jù)去重
     * */

    public static void removeDuplicate(int[] arr) {
        int i = 0, j = i + 1;
        for (; j < arr.length; j++) {
            if (arr[i] != arr[j]) {
                arr[++i] = arr[j];
            }
        }
        System.out.println(i);
        System.out.println(Arrays.toString(arr));
        int result = getResult(arr, i);
        System.out.println(result);
    }


    private static int getResult(int[] arr, int r) {
        int l = 0, sum = 0;
        while (l <= r) {
            if (arr[l] >= 0) {
                sum++;
                l++;
                continue;
            }
            if (-arr[l]==arr[r]) {
                l++;
                continue;
            }else if(-arr[l]>=arr[r]){
                l++;
            }else {
                r--;
            }
            sum++;

        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-4, -4, -4, -3, -3, -2, -1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 6, 7};
        removeDuplicate(arr);
    }