leetcode [#26]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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.

Example:
Given input array 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.

---

解决方案

public class Solution {
    public int removeDuplicates(int[] nums) {
        int N = nums.length;
        if(N == 0) return 0;
        int diff = N;
        for(int i =0; i < N-1; i++){
            if(nums[i] == nums[i+1]){
                diff--;
            }
        }
        for(int i =0; i < N-1; i++){
            if(nums[i] == nums[i+1]){
                if(i < diff-1){
                    handle(nums, i, N);
                }
            }
        }
        return diff;
    }
    private static void handle(int[] a, int index, int N){
        for(int m = 0; m <= N-index-3; m++){
            a[index+1+m] = a[index+2+m];
        }
        if(a[index] == a[index+1]){
            handle(a, index, N);
        }
    }
}

---

注意事项

1. 要求不能开辟新的数组，使用常量空间原地完成。
2. 遍历一遍得到不相同元素个数。
3. 再遍历，如果当前元素等于下一元素且当前元素下标小于(diff-1)，做如下处理：将下一元素后一个元素开始的值依次向前复制；如果移动后当前元素还等于下一元素，递归调用继续处理。
4. 该方法效率不好，discuss中vote较高的方案是：

   public class Solution {
       public int removeDuplicates(int[] nums) {
           int N = nums.length;
           int p = 0;
           for(int i = 0; i < N; i++){
               if(p == 0 || nums[i] > nums[p-1]){
                   nums[p++] = nums[i];
               }
           }
           return p;
       }
   }

该方案没有单独用一次遍历来获取不相同元素个数。只遍历一次，定义了一个下标p，它始终指向当前遍历过的元素中互不相同的元素的最后一个，同时，p++也就是不相同元素的个数。