首页 > 其他分享 >移动零(快排思想,快慢指针法)

移动零(快排思想,快慢指针法)

时间:2023-02-26 22:44:55浏览次数:51  
标签:快慢 数组 nums 元素 快排 key 排序 指针

题目:

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

思路:

限制条件

  1. 将0移动到末尾。遍历数组,找到0,
  2. 保持相对顺序。排序,或者每次找到零都要向前挪动一位
  3. 对数组进行原地操作,限制空间复杂度。不能创建一个新数组进行排序,很要命!

提示:使用双指针

  • 双指针和排序这两个关键词很容易想到快速排序,快速排序首先要确定一个待分割的元素做中间点 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的位置。
  • 由于题目要保持原有排序不变,这里使用快慢指针法。这里我们可以用 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

相关文章

  • DV仿真环境下问题定位和性能分析工具:基于PC指针,结合map文件分析函数调用轨迹以及耗时
    关键词:DV仿真,Python,map,PC等。 当DV使用复杂软件对硬件进行仿真时,由于没有类似Trace32等IDE调试环境,出现问题往往较难定位问题。同时如果想优化性能,较难直到不同流程耗时......
  • 智能指针
    1template<typenameT>2classCSmartPtr3{4public:5CSmartPtr(T*p=nullptr)6{7if(p!=nullptr)8{9......
  • 空值指针和void*指针
    1.空指针常量一个表示0值的整数常量,叫做空指针常量。例如:0,(void*)0,void*NULL空指针常量可以赋值给任何指针类型,因为它是变体类型(void*)更倾向于用NULL表示空指针常量i......
  • 时间击败100%用户的快慢指针删除链表中的倒数第n个节点算法
    //给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 ///***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNoden......
  • 数组和指针
    一维数组和指针先回忆一下,数组是由一系列类型相同的元素组成。如:charch[4];/*4个字符的数组*/intin[4];/*4个整数的数组*/floatfl[4];/*4个浮点数的数......
  • 07. 指针
    一、指针的相关概念1.1、地址与指针与变量  内存区的每一个字节都有一个编号,这就是“地址”。如果在程序中定义了一个变量,在对程序进行编译或运行时,系统就会给这个变量......
  • C语言指针错误
    以下指针代码出现的错误,因该是第二个for循环格式使用了逗号导致代码出现紊乱,但是在调试代码却没有报错。知道的回复一下。intmain(){ int*p,i,a[10]; p=a; for(i......
  • 快排&归排&二分
    快速排序voidquick_sort(intq[],intl,intr){if(l>=r)return;inti=l-1,j=r+1,x=q[l+r>>1];while(i<j){do......
  • 一、基础算法(快排,归并,二分,高精度,前缀和,差分)
    一、基础算法快速排序题目:给定你一个长度为n的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。数据范围:1≤n≤100000,所有......
  • 智能指针
    原理:智能指针是一个类,用来存储指向动态分配对象的指针,负责自动释放动态分配的对象,防止堆内存泄漏。动态分配的资源,交给一个类对象去管理,当类对象声明周期结束时,自动调用......