leetcode刷题之数组NO.4
1.题目
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。2.解法一：双指针法 2.1.思路分析
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
【leetcode刷题之数组NO.4】当看到题目后，首先重构题意：
- 未知量是什么？未知量是将所有的0移动到末尾，且保持顺序。
- 条件是什么？条件是一个数组，可以随意访问。
- 约束是什么？约束是空间复杂度为O(1)。
重构完题目后，开始根据题目思考算法： - 要将0移到末尾，还要保持顺序，那么一种办法就是利用之前题目中的删除指定元素，将0删除，然后后面的元素全部填0。
class Solution {
public:
void moveZeroes(vector& nums) {
int slow = 0;
int fast = 0;
while (fast < nums.size()) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
for (int i = slow;
i < nums.size();
i++) {
nums[i] = 0;
}
}
};
2.3.算法分析
- 该算法的时间复杂度为O(n)。
- 算法的本质就是穷举，利用计算机的计算速度，从而求得结果，而非那些高深的公式，一下子就给出了答案，那是数学。
- 在解题的时候，首先要自己思考，思考出来了，去看看有没有比自己更好的办法；没有思考出来，去看看题解，看看自己错在哪里，没有想出哪些部分以及为什么。
推荐阅读
- PMSJ寻平面设计师之现代(Hyundai）
- 太平之莲
- 闲杂“细雨”
- 七年之痒之后
- 深入理解Go之generate
- 由浅入深理解AOP
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 生活随笔｜好天气下的意外之喜
- 感恩之旅第75天
- python学习之|python学习之 实现QQ自动发送消息