给你一个 非严格递增排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums
中唯一元素的个数。
考虑 nums
的唯一元素的数量为 k
,你需要做以下事情确保你的题解可以被通过:
- 更改数组
nums
,使nums
的前k
个元素包含唯一元素,并按照它们最初在nums
中出现的顺序排列。nums
的其余元素与nums
的大小不重要。 - 返回
k
。
思路: 设置一个map,for循环遍历,如果map中没有这个项则插入,如果有说明有重复,那么删除该项,因为删除了数值,往后退一个接着循环即可。
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
let map = {};
for(let i = 0; i < nums.length; i++) {
if (!map[nums[i]]) {
map[nums[i]] = true;
} else {
nums.splice(i, 1);
i--;
}
}
return nums.length;
};
解法二:发现题目给定的题目是有序递增数组,所以可以采用指针的方式来做。采用快慢指针的方式来记录遍历的坐标。最开始时候两个指针都指向第一个数字,如果两个指针的数字相同,则快指针向前走一步,如果不同,则两个指针都向前走一步,这样当快指针走完整个数组后,慢指针当前的坐标+1就是数组中不同数字的个数。
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
var pre = 0; cur = 0; n = nums.length;
while(cur < n) {
if (nums[cur] === nums[pre]) cur++;
else nums[++pre] = nums[cur++];
}
return pre + 1;
};
解法3:for循环,解法本质上和解法2一样。
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
var res = 0;
for(var i = 1; i< nums.length; i++) {
if (nums[i] !== nums[res]) {
nums[++res] = nums[i];
}
}
return res + 1;
};