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

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

第一题：排序第二题：判断字符是否唯一第三题: 最小的k个数第四题: 单链表的排序第五题：最大数第六题：调整数组顺序使奇数位于偶数前面(二)第七题：两个数组的交集第八题：矩阵第k小第九题：数据流中的中位数第十题：栈和排序

解法一：（冒泡排序）

具体代码如下：

class Solution {
public:
    
    vector MySort(vector& arr) {
        //vector res;
        int temp;
        for(int i=0;iarr[j]){
                   temp = arr[j];
                   arr[j] = arr[i];
                   arr[i] = temp;
                }
           }
        }
        return arr;
    }
};

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

具体代码如下：

class Solution {
public:
    
    vector MySort(vector& arr) {
        Quick_Sort(arr,0,arr.size()-1);  %调用快速排序函数
        return arr;
    }
    
    void Quick_Sort(vector& 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);
    }
};

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

具体代码如下：

class Solution {
public:
    bool isUnique(string str) {
    sort(str.begin(), str.end());  
    for(int i=0;i 
解法二：（双层循环，和后续的数进行对比，查看是否相同）
 具体代码如下：
 
class Solution {
public:
    bool isUnique(string str) {
    for(int i=0;i 
解法三：（哈希表）
 具体代码如下：
 
class Solution {
public:
    bool isUnique(string astr) {
        if(astr.length() == 0)
            return true;
        //创建哈希表
        unordered_mapmap;
        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 GetLeastNumbers_Solution(vector input, int k) {
        vector res;
        int temp;
        if(0==k){
            return res;
        }else
            for(int i=0;iinput[j])
                    {
                        temp=input[j];
                        input[j]=input[i];
                        input[i]=temp;
                    }
                }
            }
        for(int i=0;i 
解法二：（快速排序）
 这里和第一题当中出现的快速排序是一样的，只是多了一步而已。测试后发现时间和空间只是优化了一点点（但是运行了一下官方给出的代码，发现没相差多少）
 
具体代码如下：
 
class Solution {
public:
    vector GetLeastNumbers_Solution(vector input, int k) {
        Quick_Sort(input,0,input.size()-1);  //调用快速排序函数
        vector res;
        for(int i=0;i& 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 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;ival=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& nums) {
        vector 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 
第六题：调整数组顺序使奇数位于偶数前面(二) 

 解法一：（不满足空间复杂度）
 将奇数和偶数分别提取出来，最后再拼到一起。
 具体代码如下：
 
class Solution {
public:
    vector reOrderArrayTwo(vector& array) {
        vector res1,res2,res;
        for(int i=0;i 
解法二：（双指针）思路很重要，没想到用什么知识点去解决就很伤
 
解题思路：
 
双指针，从数组两头向中间靠近。左边的为奇数指针，右边的为偶数指针。左边指针在没有遇到偶数时，就向右移动，遇到偶数立即停止；右边指针再没有遇到奇数时，向左边移动，遇到奇数时，进行奇偶指针元素交换。交换之后切换到奇数指针工作。这个方法只遍历一遍数组，时间o(n),空间o(1)。 
具体代码如下：
 
class Solution {
public:
    vector reOrderArrayTwo(vector& array) {
        if(array.size()<=1){
            return array;
        }
        int i=0,j=array.size()-1;  //指向vector中的元素的指针，其实就相当于下标
        while(i 
第七题：两个数组的交集 

 解题思路：
 
首先将其中一个数组进行排序然后将排序后的元素逐个插入到临时vector数组中，插入的时候还要查看与相邻元素的值是否相等，相等的话就不插入了。这样得到的临时vector数组就是排序好的无重复数字的数组，然后逐个与另一个数组进行比较，如果是相等的，那么将这个数取出来。 
具体代码如下：
 
class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
        vector res,nums3;  //res为保存结果的数组,nums3为临时排序数组
        sort(nums1.begin(),nums1.end());
        for(int i=0;i 
第八题：矩阵第k小 

 解题思路：
 
将矩阵中的全部数字都取出来再排序，然后输出第k大的数
 
具体代码如下：
 
class Solution {
public:
    int KthinMatrix(vector >& matrix, int k) {
    int n = matrix.size();   //获取方形矩阵行的大小
    vector 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 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:
    
    vector solve(int* a, int aLen) {
        stacks;//定义一个栈用来存储数据
        int n = aLen;
        vectorres;//用来返回结果
        vector vis(aLen,0);//用来标记哪个数字出现过
        for(int i = 0;i=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专栏还有相关的算法刷题文章，等待您的阅读！