题目:
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
思路:
限制条件
- 将0移动到末尾。遍历数组,找到0,
- 保持相对顺序。排序,或者每次找到零都要向前挪动一位
- 对数组进行原地操作,限制空间复杂度。不能创建一个新数组进行排序,很要命!
提示:使用双指针
- 双指针和排序这两个关键词很容易想到快速排序,快速排序首先要确定一个待分割的元素做中间点 x,然后把所有小于等于 x 的元素放到 x 的左边,大于 x 的元素放到其右边。
- hoare法:
- 是最熟悉的一种方法,其单趟排序的思路是:取区间中最左或最右边的元素为key,定义两个变量,这里假设是p和q,q从区间的最右边向左走,找到比key小的元素就停下。p从最左边向右走,找到比key大的元素就停下。然后交换p和q所指向的元素。直到pq相遇,交换key和当前位置的值。
- 快慢指针法:
- 取最左边的数为key,定义两个快慢指针,都从key的下一位往右走,fast每走一步判断一下它指向的元素是否小于key,若小于则交换fast和slow位置的元素,并且让slow向前走,直到fast走到底,结束循环。最后让slow和key位置的值交换。再返回key的位置。
- hoare法:
- 由于题目要保持原有排序不变,这里使用快慢指针法。这里我们可以用 0 当做这个中间点,把不等于 0(注意题目没说不能有负数)的放到中间点的左边,等于 0 的放到其右边。 这的中间点就是 0 本身,所以实现起来比快速排序简单很多,我们使用两个指针 i 和 j,只要 nums[i]!=0,我们就交换 nums[i] 和 nums[j]
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
while (right < n) {
if (nums[right]) {
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
};
作者:力扣官方题解
快排思想可以在对原数组操作时想到,原地排序。
标签:快慢,数组,nums,元素,快排,key,排序,指针 From: https://www.cnblogs.com/isku-ran/p/17158059.html