給定一個(gè)有序數(shù)組握侧，數(shù)組中有正數(shù)、負(fù)數(shù)或者0鸳兽，對(duì)數(shù)組中所有的數(shù)求平方后問(wèn)有多少個(gè)不同的值掂铐。
比如對(duì)于數(shù)組[-1,0,1,1,1,1]，對(duì)數(shù)組求平方后為[1,0,1,1,1,1]揍异，那么最終的結(jié)果是2全陨，因?yàn)樽詈笾挥?和1兩個(gè)不同的數(shù)；
對(duì)于數(shù)組[-1,0,1,2,3]，對(duì)數(shù)組求平方后為[1,0,1,4,9]，那么最終的結(jié)果是4蹦漠，因?yàn)樽詈髷?shù)組中為0,1,4,9這四個(gè)不同的數(shù)；
同事提到只有時(shí)間復(fù)雜度為O(n)雨涛，空間復(fù)雜度為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);
}
