A1.删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
我的解法：
思路：利用两个相邻的指针，对比值。值相等则删除指针2的值，数组长度减1，后面的值顶上来，指针2不变，但指向新的数组值，继续对比；值不等，双指针加1，继续对比；最后nums为无重复项的升序数组。
执行用时：1140ms，在所有 JavaScript 提交中击败了14.96%的用户
内存消耗：41.1MB，在所有 JavaScript 提交中击败了24.94%的用户
弊端：看到提交的结果，当时人就傻了，我果然是个菜狗，然后细细品味代码。每次删除数组中的重复值的时候，删除项后面的项都往前挪了一位，造成了大量的操作消耗。
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
if (nums.length < 2) return nums.length;
let n1 = 0;
while(n1 < nums.length - 1){
if (nums[n1] === nums[n1 + 1]) {
nums.splice(n1+1, 1);
} else {
n1++;
}
}
return nums.length;
};
优秀的解法：
思路：利用快慢指针，for遍历的次数为快指针，慢指针用来表示不同的数组值的数量。慢指针从0开始，快慢指针的值不同时，慢指针加1，将快指针的值赋值给当前慢指针的下一位项，即当前慢指针加1后的项。最后慢指针即为无重复项数组的最大下标，长度即为最终慢指针加1。
执行用时：68ms，在所有 JavaScript 提交中击败了99.22%的用户
内存消耗：40.3MB，在所有 JavaScript 提交中击败了68.61%的用户
优点：每次操作数组只改变某个数组项的值，操作较少，速度快！
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
let i=0;
for(let j=1;j<nums.length;j++){
if(nums[i]!==nums[j]){
i++;
nums[i] = nums[j]
}
}
return i+1
};
A2移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-element
我的解法：
思路：有了A1的经验，做这道题就很快有思路了，借鉴A1的解题思路，利用双指针，将数组符合要求的项与不符合要求的项调换。双指针的方向思考，同向与异向，显然是异向的思路，正向标记等于val的项，反向标记不等于val的项。
执行用时：68ms，在所有 JavaScript 提交中击败了81.11%的用户
内存消耗：37.9MB，在所有 JavaScript 提交中击败了53.00%的用户
弊端：参考了别人的优秀代码，我的这种解法因为是异向双指针不是很好理解，代码也不够简洁，但遍历的次数是小于等于n的，类似排序，不改变原数组项的个数。
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let i = nums.length -1;
for(let j = 0; j < nums.length;){
if (nums[i] !== val) {
if (nums[j] === val) {
[nums[i--],nums[j]] = [nums[j],nums[i]]
}
j++;
} else {
i--;
}
if (j > i) return j;
}
};
[0, 1, 2, 2, 3, 0, 4, 2] 2
1次 [0,1,2,2,3,0,4,2]
2次 [0,1,2,2,3,0,4,2]
3次 [0,1,2,2,3,0,4,2]
4次 [0,1,4,2,3,0,2,2]
5次 [0,1,4,0,3,2,2,2]
6次 [0,1,4,0,3,2,2,2]
nums.length=> 5
final nums=> (8) [0, 1, 4, 0, 3, 2, 2, 2]
优秀的解法：？
思路：还是利用快慢指针实现。快指针比慢指针快n个身位--n是遇见过的val个数，将快指针的非val值赋值给慢指针的项，整体来看就是将非val值往前挪。
执行用时：68ms，在所有 JavaScript 提交中击败了81.11%的用户
内存消耗：38.2MB，在所有 JavaScript 提交中击败了12.46%的用户
弊端：改变了原始数组部分项的个数，结果数组不忍直视。
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let i = 0,j = 0
const len = nums.length
while(i < len){
if(nums[i] != val){
nums[j] = nums[i]
j++
}
i ++
}
return j
};
[0, 1, 2, 2, 3, 0, 4, 2] 2
1次 [0,1,2,2,3,0,4,2]
2次 [0,1,2,2,3,0,4,2]
3次 [0,1,2,2,3,0,4,2]
4次 [0,1,2,2,3,0,4,2]
5次 [0,1,2,2,3,0,4,2]
6次 [0,1,3,2,3,0,4,2]
7次 [0,1,3,0,3,0,4,2]
8次 [0,1,3,0,4,0,4,2]
nums.length=> 5
final nums=> (8) [0, 1, 3, 0, 4, 0, 4, 2] // 3个2变成了1个2
A3两个数组的交集 II
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
我的解法：
思路：此题在双指针的解法分类下，但是并没有想到能用双指针解决，脑袋还是不够灵活啊，短路了。想到另外的解法，一个数组遍历，另一个数组要统计数字出现的次数，用Map结构倒是很合适。
执行用时：60ms，在所有 JavaScript 提交中击败了99.43%的用户
内存消耗：39.1MB，在所有 JavaScript 提交中击败了88.71%的用户
弊端：Map结构不兼容低版本浏览器和IE。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
let map2 = new Map();
nums2.forEach(m=> map2.set(m,(map2.get(m) || 0) + 1));
let res = [];
nums1.forEach(m => {
let j = map2.get(m);
if(j) {
res.push(m);
map2.set(m, --j);
}
})
return res;
};
优秀的解法：
思路：先对两个数组排序，排序后就很容易想到双指针解法了，数值相等则同步后移，否则移动较小值得指针。
执行用时：88ms，在所有 JavaScript 提交中击败了18.45%的用户
内存消耗：39.6MB，在所有 JavaScript 提交中击败了45.68%的用户
弊端：跑分不高，但是这玩意是波动的，不必太在意，兼容性也好，双指针解法。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
// 首先对两个数组排序
// 定义两个指针分别指向两个数组，判断数值是否相等
// 相等则两个指针同步后移，否则移动较小的指针
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
let l = 0, r = 0, ans = [];
while (l < nums1.length && r < nums2.length) {
if (nums1[l] === nums2[r]) {
ans.push(nums1[l]);
l++;
r++;
} else nums1[l] < nums2[r] ? l++ : r++;
}
return ans;
};
网友评论