题目
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
空间来统计数量。最快算法解法主要分为如下几步:
特殊场景判断
- 数组为 null
- 数组长度为空
- 数组长度为 1
非重复数值前移
以 [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