数组 - 从排序数组中删除重复项

题目

https://leetcode-cn.com/explore/featured/card/top-interview-questions-easy/1/array/21/

个人解法

测试用例数(个) 执行用时(ms) 战胜
161 128 65.47%
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    var cache = {};
    var index = 0;
    
    for (var i = 0 ; i < nums.length ; i++) {
        var n = nums[i];
        
        if (!cache[n]) {
            cache[n] = true;
            nums[index] = n;
            
            index++;
        }
    }
    
    return index;
};

最快解法

测试用例数(个) 执行用时(ms) 战胜
161 68 100%
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if(nums == null || nums.length == 0) return 0;
    if(nums.length == 1) return 1;
    const len = nums.length;
    let count = 0;
    for(let i = 1 ; i < len; i++){
        if(nums[count] != nums[i]){
            count++;
            nums[count] = nums[i];
        }
    }
    return ++count;
};

分析

此题的关键点如下:

审题有些疏忽,已交代为排序数组,则无需设立 cache 空间来统计数量。最快算法解法主要分为如下几步:

特殊场景判断

非重复数值前移

[1,2,2,3] 为例,复原整个过程:

// count: 0

- - - - - - - -

  i: 1
   |
[1,2,2,3]
   |
  count: 1

- - - - - - - -

    i: 2
     |
[1,2,2,3]
   |
  count: 1

- - - - - - - -

      i: 3
       |
[1,2,3,3]
     |
    count: 2

- - - - - - - -



// 由于 i 是从 1 开始,最后需要算上第 0 个
// count++

// count: 3

*****
Written by Zheng Yu on 12 March 2019