当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.026.Remove Duplicates from Sorted Array

LeetCode.026.Remove Duplicates from Sorted Array


题目描述

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 by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.

解题过程

原地移除有序数组中的重复元素。题目要求不得额外申请新数组,但超过新数组长度的元素不做要求。
使用快慢双指针:慢指针slow和快指针fast都从前往后扫描,快指针遇到非重复元素就赋值给慢指针、遇到重复元素就跳过,保证慢指针slow之前都是要保留的唯一元素

package _026_RemoveDuplicatesFromSortedArray;

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums==null || nums.length==0)
            return 0;
        int slow=0,fast=0;
        for(;fast<nums.length-1;){
            if(nums[fast] != nums[fast+1]){
                nums[slow++] = nums[fast++];
            }else{
                fast++;
            }
        }
        nums[slow++] = nums[fast];
        return slow;
    }
}

public class RemoveDuplicatesFromSortedArray {
    public static void main(String[] args){
        int[] input = {1,1,1,2,33,44,44};
        Solution solution = new Solution();
        System.out.println(solution.removeDuplicates(input));
        for(int a:input)
            System.out.print(a+" ");
    }
}

我的方法是保留连续重复元素的最后一个(所以数组最后一个元素肯定要保留),看别人都是保留连续重复元素的第一个(所以数组第一个元素肯定要保留),比如:

class Solution {
    public int removeDuplicates(int[] nums) {
        int count=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]!=nums[i-1]){
                nums[count++] = nums[i];
            }
        }

        return count;
    }
}

GitHub代码


上一篇 LeetCode.203.Remove Linked List Elements

下一篇 LeetCode.027.Remove Element

阅读
406
阅读预计2分钟
创建日期 2018-02-22
修改日期 2018-02-25
类别
百度推荐