Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1603986
  • 博文数量: 43
  • 博客积分: 169
  • 博客等级: 入伍新兵
  • 技术积分: 1162
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-08 15:35
文章分类

全部博文(43)

文章存档

2021年(1)

2019年(4)

2016年(6)

2015年(8)

2013年(19)

2012年(5)

分类: 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(主要为了处理奇数个重复的问题)

点击(此处)折叠或打开

  1. static Integer[] unique(Integer arr[]) {
  2.         if(arr == null || arr.length < 2) return arr;
  3.         Stack<Integer> stack = new Stack<>();
  4.         boolean isRepeat = false;
  5.         stack.push(arr[0]);
  6.         for (int i = 1;i< arr.length; i++) {
  7.             if(!stack.isEmpty()) {
  8.                 if(stack.peek() == arr[i]) {
  9.                     isRepeat = true;
  10.                     continue;
  11.                 }else {
  12.                     if(isRepeat) {
  13.                         stack.pop();
  14.                         if(stack.peek() == arr[i]) {
  15.                             isRepeat = true;
  16.                             continue;
  17.                         }else {
  18.                             stack.push(arr[i]);
  19.                             isRepeat = false;
  20.                         }
  21.                     }else {
  22.                         stack.push(arr[i]);
  23.                     }
  24.                 }
  25.             }else{
  26.                 stack.push(arr[i]);
  27.                 isRepeat = false;
  28.             }
  29.         }
  30.         return stack.toArray(new Integer[0]);
  31.     }

阅读(1098) | 评论(0) | 转发(0) |
0

上一篇:String、StringBuffer、StringBuilder详解之String类

下一篇:没有了

给主人留下些什么吧!~~