程序员经验分享-hwhale

必刷算法题之排序篇（题目及代码）---C++

2023-10-26

前言，该篇博客记录了和排序有关的一些题目，差不多是逐级递增的难度，后续还会补充，有具体思路和代码。

第一题：排序

在这里插入图片描述
解法一：（冒泡排序）

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        //vector<int> res;
        int temp;
        for(int i=0;i<arr.size()-1;i++){
           for(int j=i+1;j<arr.size();j++){
               if (arr[i]>arr[j]){
                   temp = arr[j];
                   arr[j] = arr[i];
                   arr[i] = temp;
                }
           }
        }
        return arr;
    }
};

解法二：（快速排序）不了解快速排序的可以点击此处了解1或 点击此处了解2

具体代码如下：

class Solution {
public:
    
    vector<int> MySort(vector<int>& arr) {
        Quick_Sort(arr,0,arr.size()-1);  %调用快速排序函数
        return arr;
    }
    
    void Quick_Sort(vector<int>& arr, int begin, int end){  %这是一个递归函数
    if(begin > end)   %说明到结束位置了
        return;
    int tmp = arr[begin];   %默认从第一个数开始比较
    int i = begin;          %首位置的哨兵
    int j = end;			%尾位置的哨兵
    while(i != j){
        while(arr[j] >= tmp && j > i){   %j的作用是找到比tmp小的数，如果没有，继续向前找
            j--;
            }    %不满足循环说明此时arr[j] < tmp或者j=i
        while(arr[i] <= tmp && j > i){   %i的作用是找到比tmp大的数，如果没有，继续向后找
            i++;
            }   %不满足循环说明此时arr[i] > tmp或者j=i
        if(j > i){    %说明此时j>i，且arr[i] > tmp或是arr[j] < tmp其中一个条件满足,那么交换两者位置的值，
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    %第一轮“探测"结束后，哨兵i、j重合了，这时候该重合点拆分成两个序列，继续递归
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
    }
};

第二题：判断字符是否唯一

在这里插入图片描述

解法一：（排序法）
解题思路如下：
step1:先对字符串进行排序
step2:出现过两次就说明重复了（判断依据：相邻的字符相等）

具体代码如下：

class Solution {
public:
    bool isUnique(string str) {
    sort(str.begin(), str.end());  
    for(int i=0;i<str.size()-1;i++){
        if(str[i]==str[i+1]){
            return false;
        }
    }
    return true;
    }
};

解法二：（双层循环，和后续的数进行对比，查看是否相同）
具体代码如下：

class Solution {
public:
    bool isUnique(string str) {
    for(int i=0;i<str.size()-1;i++){
        for(int j=i+1;j<str.size();j++){
            if(str[i]==str[j]){
                return false;
            }
        }
    }
    return true;
    }
};

解法三：（哈希表）
具体代码如下：

class Solution {
public:
    bool isUnique(string astr) {
        if(astr.length() == 0)
            return true;
        //创建哈希表
        unordered_map<char, int>map;
        for(int i = 0; i< astr.length(); i++){
            if(map.find(astr[i])!= map.end())  //如果在map中找到了对应的数，返回false
                return false;
            map[astr[i]] = i;   //否则，将这个数加入到map中
        }
        return true;
    }
};

第三题: 最小的k个数

在这里插入图片描述
解题思路：
先对数组进行排序，然后输出最小的4个数。

解法一：（冒泡排序，时间复杂度效率不高）
具体代码如下：

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        int temp;
        if(0==k){
            return res;
        }else
            for(int i=0;i<input.size()-1;i++)  %先进行排序
            {
                for(int j=i;j<input.size();j++)
                {
                    if(input[i]>input[j])
                    {
                        temp=input[j];
                        input[j]=input[i];
                        input[i]=temp;
                    }
                }
            }
        for(int i=0;i<k;i++){   %输出排序后的前k个数
            res.push_back(input[i]);
        }
        return res;
    }
};

解法二：（快速排序）
这里和第一题当中出现的快速排序是一样的，只是多了一步而已。测试后发现时间和空间只是优化了一点点（但是运行了一下官方给出的代码，发现没相差多少）

具体代码如下：

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        Quick_Sort(input,0,input.size()-1);  //调用快速排序函数
        vector<int> res;
        for(int i=0;i<k;i++){
            res.push_back(input[i]);
        }
        return res;
    }
    
    void Quick_Sort(vector<int>& arr, int begin, int end){
    if(begin > end)
        return;
    int tmp = arr[begin];                //默认从第一个数开始比较
    int i = begin;                       //首位置的哨兵
    int j = end;			             //尾位置的哨兵
    while(i != j){
        while(arr[j] >= tmp && j > i){   //满足这个条件，尾哨兵向前移动
            j--;
            }                            //不满足循环说明此时arr[j] < tmp或者j=i
        while(arr[i] <= tmp && j > i){  //满足这个条件，首哨兵向后移动
            i++;
            }                           //不满足循环说明此时arr[i] > tmp或者j=i
        if(j > i){                      //说明此时j!=i，而是arr[i] > tmp、arr[j] < tmp,那么交换两者位置的值，
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    //第一轮“探测"结束后，哨兵i、j重合了，这时候该重合点拆分成两个序列，继续递归
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
    }
};

解法3：（大根堆—有兴趣的读者可自行搜索，笔者对这方面的知识点不怎么清楚）

第四题: 单链表的排序

在这里插入图片描述
解题思路：

先将无序链表中的数据依次存放在一个vector数组当中，然后对vector数组进行排序，排完序后依次将数据赋给链表头，最后返回链表头（借助临时链表）
具体代码如下：

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        vector<int> res;
        ListNode* pres=head;  //创建临时链表，用于保存排序之后的数组
        while(pres){
            res.push_back(pres->val);
            pres=pres->next;
        }
        pres=head;  //记得将链表的指针重新指向链表头
        sort(res.begin(),res.end());  //进行排序
        for(int i=0;i<res.size();i++){
            pres->val=res[i];
            pres=pres->next;
        }
        return head;   //返回真正的链表头
    }
};

时间复杂度： O(nlog2n)O(nlog_2n)O(nlog2​n)，sort函数的复杂度
空间复杂度： O(n)O(n)O(n)，存储链表元素值的辅助数组长度n

第五题：最大数

在这里插入图片描述
解题思路：

  • 定义一个字符数组，通过for循环将数字转换成字符
  • 对字符数组进行排序
  • 设置排序规则
  • 输出字符数组

具体代码如下：

class Solution {
public:
    static bool cmp(string a,string b){
    	return a+b>b+a;
    }
    string solve(vector<int>& nums) {
        vector<string> temp;
        for(int i = 0;i < nums.size();i++){
        	temp.push_back(to_string(nums[i]));
        }
        sort(temp.begin(),temp.end(),cmp);  //对字符数组进行排序，cmp为排序规则
        if(temp[0]=="0"){
        	return "0";
        }
        string res;
        for(int i=0;i<temp.size();i++){
        	res+=temp[i];
        }
        return res;
    }
};

第六题：调整数组顺序使奇数位于偶数前面(二)

在这里插入图片描述
解法一：（不满足空间复杂度）
将奇数和偶数分别提取出来，最后再拼到一起。
具体代码如下：

class Solution {
public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        vector<int> res1,res2,res;
        for(int i=0;i<array.size();i++){
            if(array[i]%2==1){    //说明是奇数
                res1.push_back(array[i]);
            }else{
                res2.push_back(array[i]);
            }    
        }
        for(int i=0;i<res1.size();i++){
            res.push_back(res1[i]);
        }
        for(int i=0;i<res2.size();i++){
            res.push_back(res2[i]);
        }
        return res;
    }
};

解法二：（双指针）思路很重要，没想到用什么知识点去解决就很伤

解题思路：

  • 双指针，从数组两头向中间靠近。左边的为奇数指针，右边的为偶数指针。
  • 左边指针在没有遇到偶数时，就向右移动，遇到偶数立即停止；右边指针再没有遇到奇数时，向左边移动，遇到奇数时，进行奇偶指针元素交换。交换之后切换到奇数指针工作。
  • 这个方法只遍历一遍数组，时间o(n),空间o(1)。

具体代码如下：

class Solution {
public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        if(array.size()<=1){
            return array;
        }
        int i=0,j=array.size()-1;  //指向vector中的元素的指针，其实就相当于下标
        while(i<j){
            if(array[i]%2==1){
                i++;
            }
            if(array[j]%2==0){
                j--;
            }
            if(array[i]%2==0&&array[j]%2==1){  //下面也可以直接用swap(array[i], array[j]);
                int temp;
                temp=array[j];
                array[j]=array[i];
                array[i]=temp;
                i++;
                j--;
            }
        }
        return array;
    }
};

第七题：两个数组的交集

在这里插入图片描述
解题思路：

  • 首先将其中一个数组进行排序
  • 然后将排序后的元素逐个插入到临时vector数组中，插入的时候还要查看与相邻元素的值是否相等，相等的话就不插入了。
  • 这样得到的临时vector数组就是排序好的无重复数字的数组，然后逐个与另一个数组进行比较，如果是相等的，那么将这个数取出来。

具体代码如下：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res,nums3;  //res为保存结果的数组,nums3为临时排序数组
        sort(nums1.begin(),nums1.end());
        for(int i=0;i<nums1.size();i++){
            nums3.push_back(nums1[i]);
            if(nums1[i]==nums1[i+1]){
                nums3.pop_back();
            }
        }
        for(int i=0;i<nums3.size();i++){
            for(int j=0;j<nums2.size();j++){
                if(nums3[i]==nums2[j]){
                    res.push_back(nums3[i]);
                    break;
                }
            }
        }
        return res;
        
    }
};

第八题：矩阵第k小

在这里插入图片描述
解题思路：

将矩阵中的全部数字都取出来再排序，然后输出第k大的数

具体代码如下：

class Solution {
public:
    int KthinMatrix(vector<vector<int> >& matrix, int k) {
    int n = matrix.size();   //获取方形矩阵行的大小
    vector<int> nums(n*n);   //定义一个一维数组用于保存矩阵中的所有数据
    int index = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
           nums[index++] = matrix[i][j];
        }
    }
    sort(nums.begin(), nums.end());  //对一维数组进行排序
    return nums[k - 1];    
    }
};

第九题：数据流中的中位数

在这里插入图片描述
这个题目要多读几遍，不然都不清楚要做什么（因为代码的主框架有点不一样）。
答题代码模板如下：

class Solution {
public:
    void Insert(int num) {
        
    }

    double GetMedian() { 
    
    }

};

题目大意：
设计一个类，它有两个方法，Insert(num)可以插入一个数num，GetMedian()返回所有插入的数中的中位数（若一共插入了偶数个，则取中间两个数的平均值；若一共插入了奇数个，则取中间一个即可）

具体代码如下：

class Solution {
public:
    vector<int> res;
    void Insert(int num) {
        res.push_back(num);
    }

    double GetMedian() { 
        sort(res.begin(),res.end());
        if(res.size()%2==0){
            return (res[res.size()/2-1]+res[res.size()/2])/2.00;
        }else{
            return res[res.size()/2];   // 为奇数则返回中间的数
        }
    }

};

第十题：栈和排序

在这里插入图片描述
题目要求：

  • 给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈
  • 在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列

补充：（字典序）
字典序是基于字母顺序排列的单词按字母顺序排列的方法。
英文中的 字母表（Alphabet） 按照如下的顺序排列：

ABCDEFG HIJKLMN OPQRST UVWXYZ
abcdefg hijklmn opqrst uvwxyz

本题要求的最大字典序，其实是倒过来的（从后往前找,后面的总是小于等于前面的元素才能保证子序列按字典序排列）

解题思路：
这道题文字描述有点复杂，感兴趣的小伙伴可以点击下面这个链接，有视频讲解。当然了，如果能看懂下面编写的代码，那是最好不过的了。

具体代码如下：

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        stack<int>s;//定义一个栈用来存储数据
        int n = aLen;
        vector<int>res;//用来返回结果
        vector<bool> vis(aLen,0);//用来标记哪个数字出现过
        for(int i = 0;i<aLen;i ++){//遍历数组
            s.push(a[i]);//压入栈
            vis[a[i]] = 1;//压入一个数就把对应的数字标记为1
            while(n && vis[n]) n--;//检测现有栈中最大的几个数是否都出现了（出现了就将当前未出现的最大的数n减去1），
            while(!s.empty() && n <= s.top()){  //如果先前比n大的数没有弹出（因为n改变了），那么先将先前的数弹出
                //然后将栈中>=n的元素出栈
                res.push_back(s.top());
                s.pop();
            }
        }
        //如果栈没为空就按照栈中原样直接出栈
        while(!s.empty()){
            int temp = s.top();
            res.push_back(temp);
            s.pop();
        }
        return res;
    }
};

注： 以上题目都是在牛客网的剑指offer题库中刷的，有自己做的，也有不会做看别人精华解题思路，然后总结的。如果侵犯了您的权益，请私聊我。
最后，觉得本文内容对你有所帮助的话，感谢您能点赞收藏，在我的剑指offer专栏还有相关的算法刷题文章，等待您的阅读！

导航链接：必刷算法题—二分查找（C++）
导航链接：必刷算法题—哈希篇（C++）
导航链接：剑指—动态规划篇（C++）
导航链接：剑指—树篇(C++)
导航链接：剑指—链表篇（C++）
导航链接：剑指—队列&栈篇（C++）

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

剑指offer

算法

面试

c

排序算法

必刷算法题之排序篇（题目及代码）---C++ 的相关文章

随机推荐

  • tensorflow 多GPU编程 完全指南

    人生苦短 我用pytorch 推荐大家使用 PyTorch分布式训练简明教程 PyTorch分布式训练基础 DDP使用 知乎 主要变动的位置包括 1 启动的方式引入了一个多进程机制 2 引入了几个环境变量 3 DataLoader多了一个s

  • 5折交叉验证的回归分析

    w lt read csv C Users Administrator Desktop mg csv header T 样本的个数为1385 5折交叉验证 n 1385 zz1 1 n zz2 rep 1 5 ceiling 1385 5

  • PTA 7-15 计算圆周率 (15 分)

    根据下面关系式 求圆周率的值 直到最后一项的值小于给定阈值 2 1 31 3 52 3 5 73 3 5 7 2n 1 n 输入格式 输入在一行中给出小于1的阈值 输出格式 在一行中输出满足阈值条件的近似圆周率 输出到小数点后6位 输入样例

  • 音视频基础（1）音视频处理流程

    文章目录 音视频基础 1 音视频处理流程 1 概要 2 音频处理流程 3 视频处理流程 4 直播客户端处理流程 5 音频数据流转 音视频基础 1 音视频处理流程 理解音频处理流程对我们做音视频开发至关重要 因为理解了这个处理流程之后 我们就

  • mysql用户授权

    mysql用户授权 1 grant授权 授权 添加用户并设置权限 命令格式 grant 权限列表 on 库名 表名 to 用户名 客户端地址 identified by 密码 with grant option with grant opt

  • draw.io环境搭建

    为什么80 的码农都做不了架构师 gt gt gt 前言 draw io是一款在github上的开源产品 由于需要构建在线文档 需要插入画图类型 对比多款开源产品 最终选择了draw io draw io图标资源非常的丰富 方便导入图标资源

  • Android——（高级控件下拉框与搜索框）

    1 高级控件与低级控件区别 是否使用适配器 2 适配器种类和作用 2 1 种类 数组适配器 ArrayAdapter new ArrayAdapter

  • MySQL - java链接mysql8 并兼容链接mysql5 亲测可用

    开始之前先去官网捋一遍 MySQL Connector J开发人员指南 看看官方的一些变动 和一些可能要注意的点 或者一些可能会踩到的坑 事先 我们要有一个使用mysql5 x的应用或者服务 需要修改的部分不算多 但是要想同时想兼容5 x和

  • java: cannot find symbol symbol: variable log

    使用Intellij idea的时候 编译项目始终报错java cannot find symbol symbol variable log 装Lombok Plugin 插件 设置 build execution deployment g

  • react-redux库

    安装react redux tnpm i react redux 未优化前 src components Count index tsx import React useState from react export default fun

  • UE4命令行打包项目

    RunUAT bat在ue安装路径找 1 Compiling the client 编译客户端的命令行代码 RunUAT BuildCookRun project full project path and project name upr

  • MySQL 命令环境变量设置方法

    安装完MySQL之后 大家可以直接打开MySQL的client输入命令 操作MySQL数据库 当然也可以使用dos窗口输入MySQL命令操作MySQL数据库 方法1 1 打开dos窗口 具体怎么打开 百度 2 定位到MySQL安装目录下的b

  • jmeter生成随机数

    打开函数助手 Random 写入随机范围的最小值 和最大值 name of variable in which to store the result 为变量名 写好后 点击生成 复制字符串 粘贴到需要的请求上即可

  • linux查看vlan命令,[转]linux VLAN配置(vconfig)

    1 安装vlan vconfig 和加载8021q模块 aptitude install vlan modprobe 8021q 2 使用linux vconfig命令配置vlan vconfig add eth0 100 vconfig

  • 网络安全——cobalt Strike 之office钓鱼

    一 office钓鱼 在无需交互 用户无感知的情况下 执行office文档中内嵌的恶意代码 例如宏 从远控地址中下载并运行恶意可执行程序 例如远控木马 勒索病毒等 cobalt strike office钓鱼原理 主要生成一段vba代码 然

  • 前端发送的form-data类型name=“carNumber“的参数后端怎么接收

    需求 前端将图片和其他信息一起已form data类型发送给后端 图片以二进制流的形式 其他信息以key value的键值对的形式 举例 具体荷载 后端controller层接收的方法 RequestMapping value upload

  • linux安装jdk8

    1 官网下载链接 Java Downloads Oracle 2 下载完成之后 我们打开linux 执行如下命令 最后通过rz命令将文件上传 root localhost local mkdir usr local java root lo

  • android imageloader 进度条,Android-Universal-Image-Loader使用介绍

    图片开源库是一个应用非常广泛的第三方库 几乎所有的应用都会使用 目前而言常见的图片库有 Android Universal Image Loader Picasso Fresco Glide等 下面是国内Top500Android应用分析报

  • Win10笔记本屏幕最低亮度依旧很亮？最高亮度依旧很暗？

    左下角搜索 显卡 打开 英特尔R显卡控制中心 点击 显示器 点击 颜色 里面有 全部颜色 在这里调节即可 嫌太亮 调低些 反之则反

  • 必刷算法题之排序篇（题目及代码）---C++

    前言 该篇博客记录了和排序有关的一些题目 差不多是逐级递增的难度 后续还会补充 有具体思路和代码 文章目录 第一题 排序 第二题 判断字符是否唯一 第三题 最小的k个数 第四题 单链表的排序 第五题 最大数 第六题 调整数组顺序使奇数位于偶

热门标签