Chinaunix首页 | 论坛 | 博客
  • 博客访问: 73693
  • 博文数量: 16
  • 博客积分: 31
  • 博客等级: 民兵
  • 技术积分: 187
  • 用 户 组: 普通用户
  • 注册时间: 2010-11-19 19:58
个人简介

一步一个阶梯,向人类进化。

文章分类

全部博文(16)

文章存档

2018年(1)

2015年(3)

2014年(11)

2013年(1)

我的朋友

分类: Java

2014-12-29 15:54:09

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

删除数组中重复的元素,要求空间复杂度为O(1),即只能在原数组操作,不能开辟新内存。
基本思想:数组既然是排好序的,就可以从头向尾遍历,由于最后的结果肯定比原数组元素少,所以把不重复的元素从头到尾依次把原来的内容覆盖。复制过程需要两个指针,一个指针代表去重前的遍历指针1,另一个代表去重后的新数组的指针2,如果当前元素和前一个元素不重复,就保留,同时指针2后移;如果重复,则只后移指针1。

点击(此处)折叠或打开

  1. public class Solution {
  2.     public int removeDuplicates(int[] A) {
  3.         if(A.length == 0){
  4.             return 0;
  5.         }
  6.         int position = 0;
  7.         int i = 1;
  8.         while(i < A.length){
  9.             if(A[i] != A[position]){
  10.                 A[++ position] = A[i];
  11.             }
  12.             i ++;
  13.         }
  14.         return position + 1;
  15.     }
  16. }


阅读(882) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~