- 博客访问： 1581998
- 博文数量： 43
- 博客积分： 169
- 博客等级： 入伍新兵
- 技术积分： 1162
- 用 户 组： 普通用户
- 注册时间： 2012-04-08 15:35
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： java
2021-06-08 14:25:00
算法描述：
给定一个数组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（主要为了处理奇数个重复的问题）
给定一个数组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]);
- }
给主人留下些什么吧！~~