解题思路:
\qquad 适用双指针,l
:最左边‘0’元素坐标;r
:l
右边第一个非零元素坐标。
\qquad 最初的思路:将l
和r
初始化为0,遍历数组nums
若任意一个指针到达数组末尾时停止。若当前nums[l] == 0
则移动r++
,找到第一个非零元素时交换二者的值;否则nums[l] != 0
则移动l++
,去寻找0元素。每次仅移动一次指针(l
或r
)。
\qquad 这个思路虽然可行,但实现代码仍有些繁琐,需要同时移动两个指针,并且考虑两个指针的范围问题。其优化的版本早已在快速排序的思想中体现。
优化思路:
\qquad l
:假设以其为分界点,左边均为非零元素,右边均为0元素;
\qquad r
:不断向右探索的指针,直至遍历到数组最后一个元素停止。
\qquad 初始化l = 0
,r = 0
。
\qquad 当nums[r] != 0
,将nums[l]
与nums[r]
的值交换,同时l
右移1,以保证假设成立。若数组中无0元素,在移动过程中l = r
;当存在0元素时,l
与r
才会拉开距离,且nums[r]
始终指向第一个0元素。
\qquad 很多算法题的解题思路,都与数学归纳法类似。要创造自己一个假设,并在每一步都要做与假设一致的操作,维持假设成立,最后将假设变成“现实”。最重要的是如何找到一个最合适的假设。
优化代码:
\qquad 1)使用swap(a,b)
函数交换变量的值。而非使用中间变量temp
进一步简化代码。 (头文件#include<algorithm>
)
class Solution {
public:void moveZeroes(vector<int>& nums) {int l = 0, r = 0;while(r < nums.size()){if(nums[r] != 0){swap(nums[l], nums[r]);l++;}r++;}}
};