算法描述:
给定一个数组int arr[], 相邻元素去重,同时去重后得到的新数组保证相邻元素不重复。
例子:
int arr[] = new int[] {1,2,3,6,6,6,3,5,7,7,8
}
去重后结果:[1, 2, 5, 8 ]
这里给一个时间复杂度O(n) 空间复杂度O(n)的算法:
采用java中的Stack作为临时存储空间,外加一个临时变量 isRepeat(主要为了处理奇数个重复的问题)
-
static Integer[] unique(Integer arr[]) {
-
if(arr == null || arr.length < 2) return arr;
-
Stack<Integer> stack = new Stack<>();
-
boolean isRepeat = false;
-
stack.push(arr[0]);
-
for (int i = 1;i< arr.length; i++) {
-
if(!stack.isEmpty()) {
-
if(stack.peek() == arr[i]) {
-
isRepeat = true;
-
continue;
-
}else {
-
if(isRepeat) {
-
stack.pop();
-
if(stack.peek() == arr[i]) {
-
isRepeat = true;
-
continue;
-
}else {
-
stack.push(arr[i]);
-
isRepeat = false;
-
}
-
}else {
-
stack.push(arr[i]);
-
}
-
}
-
}else{
-
stack.push(arr[i]);
-
isRepeat = false;
-
}
-
}
-
return stack.toArray(new Integer[0]);
-
}
阅读(1098) | 评论(0) | 转发(0) |