共计 1215 个字符，预计需要花费 4 分钟才能阅读完成。
[TOC]
前端与算法 leetcode 283. 移动零
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
283. 移动零
概要
这个问题属于“数组变换”的一个广泛范畴。这一类是技术面试的重点。主要是因为数组是如此简单和易于使用的数据结构。遍历或表示不需要任何样板代码，而且大多数代码将看起来像伪代码本身。[[1]]
问题的要求很简单, 将所有 0 移动到数组末尾且非 0 元素必须保持其原始顺序
提示
双指针, 暴力法
解析
有意思的是, 正常设计的算法, 在遇到 [0,0,0,0,1],[1,0,0,0,0,1] 这两种数组的时候都比较尴尬, 没办法有效的减少操作次数, 这两个需求是相互排斥的, 但是我们可以尽可能的在其中找到平衡
解法一: 暴力法
暴力法使用一个 额外的数组 , 先将所有非 0 元素按照原顺序 push 到数组里同时用count 统计 0 出现的次数, 然后在 额外的数组 里再 pushcount个 0, 按照题目的要求我们需要在原来的数组上改动, 所以再依次将数组元素填入原数组
<!– #### 复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(n) –>
解法二: 双指针法
前一种方法有一些额外的操作. 例如, 所有 (除最后一个) 前导零的数组:[0,0,0,1]就会对数组进行许多不必要的操作, 如果只固定非 0 元素的话, 可以只交换一次
算法
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
// 双指针法
for (let [i, j] = [0, 0]; i < nums.length; i++) {if (nums[i] !== 0) {[nums[j], nums[i]] = [nums[i], nums[j]]
j++
}
}
// 暴力法
// let count = 0 // 统计 0 的个数
// const res = [] // 返回的数组
// nums.forEach(el => el === 0 ? count++ : res.push(el))
// for (let i = 0; i < count; i++) {// res.push(0)
// }
// for (let i = 0; i < nums.length; i++) {// nums[i] = res[i]
// }
}传入 [0,1,0,3,12] 的运行结果
[1,3,12,0,0]执行结果
执行用时 :68 ms, 在所有 javascript 提交中击败了 95.54% 的用户
内存消耗 :37.2 MB, 在所有 javascript 提交中击败了 5.10% 的用户GitHub 仓库
350. 两个数组的交集 II
<!– ## 引用列表 –>
<!– leetcode,leetcode-cn,[J],283. 两个数组的交集 II, –>
正文完
发表至： javascript
2019-11-21
