Sort相关题目

LC 148. 排序链表

题目链接: 148. 排序链表

1. 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

链表排序相关算法
(1) 插入排序：时间复杂度 O($n^2$), 空间复杂度 O(1);
(2) 归并排序(自顶向下) 时间复杂度 O($nlogn$), 空间复杂度 O($logn$);
(3) 归并排序(自底向上) 时间复杂度 O($nlogn$), 空间复杂度 O($1$);
(4) 利用辅助空间进行快排 时间复杂度 O($nlogn$), 空间复杂度 O($n$);

(1)插入排序代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) 
    {
        if(!head) return nullptr;
        auto dummy = new ListNode(0,head);
        auto node = dummy->next, next = node->next, pre = dummy;
        node->next = nullptr;
        node = next;
        while(node)
        {
            next = node->next;
            pre = dummy;
            while(pre->next && pre->next->val < node->val) pre = pre->next;
            node->next = pre->next;
            pre->next = node;
            node = next; 
        }
        auto res = dummy->next;
        delete dummy;
        return res; 
    }
};

用到头插法重建链表的思想，但由于时间复杂度太高，TLE了。

(2)归并排序(自顶向下) 代码实现

class Solution 
{
public:
     ListNode* merge_sort(ListNode *n1, ListNode *n2)
    {
        auto dummy = new ListNode(0); 
        auto node = dummy;
        while(n1 && n2) 
        {
            if(n1->val <= n2->val) node->next = n1, n1 = n1->next;
            else node->next= n2, n2 = n2->next;
            node = node->next; 
        }

        if(n1) node->next = n1; 
        if(n2) node->next = n2; 
        auto res = dummy->next;
        delete dummy;
        return res; 
    }

    ListNode* sortList(ListNode *head, ListNode *tail)
    {
        if(!head) return nullptr; 
        if(head->next == tail)              // 递归处理当只有一个元素时的next指向nullptr; 
        {
            head->next = nullptr; 
            return head; 
        }

        // 快慢指针找到链表的中间结点 
        auto fast = head, slow = head; 
        while(fast != tail)          
        {
            slow = slow->next;  fast = fast->next; 
            if(fast != tail) fast = fast->next; 
        }
        auto mid = slow; 
        return merge_sort(sortList(head, mid), sortList(mid, tail)); 

    }

    ListNode* sortList(ListNode* head) 
    {
        return sortList(head, nullptr);

    }
};

(3)归并排序(自底向上) 代码实现

class Solution
{
public:
    ListNode* List_Merge(ListNode *n1, ListNode *n2)
    {
        ListNode *dummy = new ListNode(0);
        auto temp = dummy;
        while(n1 && n2)
        {
            if(n1->val <= n2->val) temp->next = n1, n1 = n1->next;
            else temp->next = n2, n2 = n2->next;
            temp = temp->next;
        }
        if(n1) temp->next = n1;
        if(n2) temp->next = n2; 
        auto res = dummy->next;
        delete dummy;
        return res; 
    }

    ListNode* sortList(ListNode* head) 
    {
        if(!head) return nullptr;

        int len = 0; 
        auto node = head;
        while(node) ++len, node = node->next;       

        ListNode *dummy = new ListNode(0, head); 

        for(int substr_len = 1; substr_len < len; substr_len <<= 1)
        {
            ListNode *pre = dummy, *cur = dummy->next; 
            while(cur)
            {
                auto head1 = cur;
                for(int i = 1; i < substr_len && cur->next; ++i) cur = cur->next;

                auto head2 = cur->next;
                cur->next = nullptr; 
                cur = head2;
                for(int i = 1; i < substr_len && cur && cur->next; ++i) cur = cur->next; 

                ListNode *next = nullptr;
                if(cur) next = cur->next, cur->next = nullptr; 
                ListNode *res = List_Merge(head1, head2);
                pre->next = res;
                while(pre->next) pre = pre->next; 
                cur = next; 
            }
        }

        auto res = dummy->next;
        delete dummy;
        return res; 
    }
};

相比于自顶向下，其从长度为1的子串开始排序合并，通过迭代的方式取代自顶向下的递归过程。 所以将空间复杂度降低到了 O(1);

(4) 利用辅助空间进行快排

class Solution {
public:
    ListNode* sortList(ListNode* head) 
    {
        if(!head) return nullptr;
        vector<ListNode*> vec;
        while(head) vec.push_back(head), head = head->next; 

        sort(vec.begin(), vec.end(), 
            [](ListNode *n1, ListNode *n2) -> bool
            {
                return n1->val < n2->val;
            }); 

        auto node = vec.front();
        for(auto iter = vec.begin() + 1; iter != vec.end(); ++iter) node->next = *iter, node = node->next;
        node->next = nullptr;
        return vec.front();
    }
};

相比于插入排序, 这里用空间换了时间， 也是几种方案中空间复杂度最高的一个方案。

LC 56. 合并区间

题目链接: 56. 合并区间

1. 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

class Solution 
{
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
    {
        int s1 = -1, e1 = -1; 
        vector<vector<int>> res; 
        sort(intervals.begin(), intervals.end(),
            [](vector<int> &n1, vector<int> &n2) -> bool
            {
                return n1[0] < n2[0];
            });

        for(auto &vec : intervals)
        {
            if(s1 == -1 && e1 == -1) s1 = vec[0], e1 = vec[1]; 
            else 
            {
                int v1 = vec[0], v2 = vec[1]; 
                if(v1 > e1)
                {
                    res.push_back({s1, e1});
                    s1 = v1, e1 = v2; 
                } 
                else if(v2 > e1) e1 = v2; 
             }
        }
        res.push_back({s1, e1}); 
        return res; 
    }
};

主要思路 : 首先将我们intervals各个区间根据其左端点进行升序排序， 这样我们每次拿到一个新区间的时候，我们检测一下新区间的左端点，(1) 若这个新区间的左端点比目前区间的右端点还大，说明旧区间和此时的新区间必然是两个不同的区间，故此时旧区间就是一个独立的区间。(2) 若此时新区间的左端点小于目前区间的右断点，说明此时区间存在重叠部分，我们比较新区间的右端点和旧区间右端点，若新区间右端点小于旧区间的右端点，说明旧区间包含了新区间，此时旧区间并不需要更新，否则新区见右端点大于旧区间右端点，则将此时旧区间的右端点更新为新区间的右端点。 当遍历完所有的区间时，退出for循环，此时用于比较的区间说明已经是一个独立的区间了。

LC 179. 最大数

题目链接: 179. 最大数

1. 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
   注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例

输入：nums = [10,2]
输出："210"

输入：nums = [3,30,34,5,9]
输出："9534330"

输入：nums = [1]
输出："1"

输入：nums = [10]
输出："10"

思路分析

对于这个组成的最大数需要满足的一个性质为其中任意两个相邻元素为 x 和 y,，如果其排序为x y 那么这种情况下 x y 组成的数字的大小一定要大于等于 y x这种顺序组成的数字。 那么我们可不可以利用这个来进行排序呢。 即能否证明这里面每两个元素之间能否进行比较。

一个二元运算符可以进行排序，等价于它是一个全序关系。 所谓全序关系，自然也是一种二元关系。全序是指，集合中的任两个元素之间都可以比较的关系。

1. 设集合X上有一全序关系，如果我们把这种关系用 ≤ 表述，则下列陈述对于 X 中的所有 a, b 和 c 成立：
   (1) 如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)
   (2) 如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)
   (3) a ≤ b 或 b ≤ a (完全性)

证明:
1. 首先(3) 完全性比较好证， 对于任意两个元素组成的数字必然有 xy ≤ yx 或者 xy ≤ yx;
2. 证明(1) 反对称性, xy ≤ yx 且 yx ≤ xy –> xy == yx —> x = y;
3. 证明(2) 传递性, 这里设一下 x 的长度为len(x) = n, y 的长度为 len(y) = m, z的长度为len(z) = k; 则 xy 表示的数值大小为 x * $10^m$ + y, yx 表示的数值大小为 y * $10^n$ + x; 则由于xy ≤ yx, 则整理得到 x / y ≤ $10^n - 1$ / $10^m - 1$; 由于yz ≤ zy , 整理得到 y / z ≤ ($10^m - 1$) / ($10^k - 1$);故两个式子经过运算可以得到 x / z ≤ ($10^n - 1$) / ($10^k - 1$); 即满足 xz ≤ zx的这个关系，传递性可证。

满足上面三条性质则说明这个关系是一个全序关系，故我们可以直接将这个序列按照我们的规则sort一遍即为正确的答案。

实现代码

class Solution {
public:
    string largestNumber(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end(), 
            [](int a, int b)->bool
            {
                string s1 = to_string(a), s2 = to_string(b);
                return s1 + s2 > s2 + s1;
            });
        string res;
        for(auto str : nums) res += to_string(str);
        int k = 0;
        while(k < res.size() - 1 && res[k] == '0') ++k;   // 去除前导0
        return res.substr(k);                             // 返回去除前导0后的子串. 
    }
};

LC 75. 颜色分类

题目链接: 75. 颜色分类
1. 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
*此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

输入：nums = [2,0,1]
输出：[0,1,2]

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

输入：nums = [1]
输出：[1]

当然这道题目我们直接快排一遍是能过的，但这样的话时间复杂度就是O(nlogn)的了， 我们能不能在一个仅使用常数空间的一趟扫描算法吗？

思路

其实我们nums中只有0, 1, 2这三个元素，最后排序完成的话，前半部分肯定是0, 后半部分肯定是2, 剩下的中间部分就是1了， 所以我们的简单的思路就是从头遍历一遍，如果当前数字为0，把它放到前面部分，如果当前数字为2，把它放到后面部分，如果为1，则跳过。即我们在这个过程设置两个指针，一个指向0元素应存放的位置，一个指向2元素应存放的位置。

代码实现

class Solution 
{
public:
    void sortColors(vector<int>& nums) 
    {
        for(int i = 0, pos_0 = 0, pos_2 = nums.size() - 1; i <= pos_2; ++i)
            if(nums[i] == 0) swap(nums[i], nums[pos_0++]);
            else if(nums[i] == 2) swap(nums[i], nums[pos_2--]), nums[i] != 1 ? --i:i;
    }
};

代码分析

从i = 0 开始遍历, 若当前遍历的数字为1则不需要做任何操作，我们可以发现由于i为工作指针,一定比 pos_0指针位置靠后，故pos_0指针所指向的当前位置所对应的元素一定是1，故如果这两个位置的数字发生交换, 一定可以判断是0 和 1 (也可能是0 和 0 交换)之间进行的交换， 故此时i 指针和 pos_0指针往后走一步没毛病， 但如果i遍历到的是2, 就需要跟pos_2指向的元素交换, 由于pos_2的位置在i指针前面, 我们无法得知此时pos_2指向的元素到底是什么，如果此时pos_2指向的元素是1， 那么没毛病, 交换完毕后, i++, pos_2–,如果pos_2指向的元素可能是0 , 2 , 此时i指针不能往后走,因为要判断下当前被交换过来的元素是交换到前面还是交换到后面，但pos_2要往前走一步,指到前面的一个未知元素。

LC 215. 数组中的第K个最大元素

题目链接: 215. 数组中的第K个最大元素

1. 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

思路

同样这道题，我们可以按升序sort一遍过， 但是题目的要求并不是让我们把nums数组变为升序，而是要求返回第k大的元素， 故这里用的快速选择算法，即快选，其时间复杂度为 O($n$)。

代码实现

class Solution {
public:
    void quick_sort(vector<int>& nums, int l, int r, int k)
    {
        if(l >= r) return;
        int i = l - 1, j = r + 1, base = nums[l + r >> 1];
        while(j > i)
        {
            do ++i;while(nums[i] > base);
            do --j;while(nums[j] < base);
            if(j > i) swap(nums[i], nums[j]); 
        }
        int len = j - l + 1;
        if(k <= len) quick_sort(nums, l, j, k);
        else quick_sort(nums, j + 1, r, k - len);
    }

    int findKthLargest(vector<int>& nums, int k) 
    {
        quick_sort(nums, 0, nums.size() - 1, k);
        return nums[k - 1];
    }
};

LC 4. 寻找两个正序数组的中位数

题目链接: 4. 寻找两个正序数组的中位数

1. 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

输入：nums1 = [], nums2 = [1]
输出：1.00000

输入：nums1 = [2], nums2 = []
输出：2.00000

思路分析

由于这是两个有序序列，我们很容易想到链表的合并中使用的双指针算法，即找到合并后的 ( nums1.size() + nums2.size() / 2 个数，如果总数是偶数还要找出两个算平均值， 这种算法的时间复杂度为O($n$) , 而题目的进阶要求是要我们实现一个O($log(m + n)$)的算法;

class Solution 
{
public:
    int mfind(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
    {
        if(nums1.size() - i > nums2.size() - j) return mfind(nums2, j, nums1, i, k);
        if(k == 1)
        {
            if(nums1.size() == i) return nums2[j];
            else return min(nums1[i], nums2[j]);
        }
        if(nums1.size() == i) return nums2[j + k - 1] ;
        int si = min(i + k / 2, (int)nums1.size()), sj = j + k - k / 2;
        if(nums1[si - 1] > nums2[sj - 1]) return mfind(nums1, i, nums2, sj, k - (sj - j));
        else return mfind(nums1, si, nums2, j, k - (si - i)); 
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        int n = nums1.size() + nums2.size();
        if(n % 2 == 0)
        {
            int left = mfind(nums1, 0, nums2, 0, n / 2);
            int right = mfind(nums1, 0, nums2, 0, n / 2 + 1);
            return (left + right) / 2.0;
        }
        else return mfind(nums1, 0, nums2, 0, n / 2 + 1); 
    }
};

代码分析

1. 首先判断nums1 和 nums2的元素总的个数n的奇偶情况，若为奇数，则找到一个数即可， 若为偶数则找到中间的两个数然后取平均值。

2. 然后在mfind函数中, 参数说明(vector[HTML_REMOVED] &nums1, int i, vector[HTML_REMOVED] &nums2, int j, int k)， nums1为序列1, i 表示从序列1的下标为i的元素开始找， nums2为序列2， j表示从序列2的下标为j的元素开始寻找， k为要找到两个有序序列合并成一个新有序序列的后的第k个数。 这里假如的是nums1为长度较短的序列， 如果nums1的长度比nums2长，则将这nums1, i这两个参数和nums2， j 这两个参数的位置进行交换。

3. 特判 ： 若 k = 1, 说明只需找一个数， 由于nums1为较短序列，故先判断下是否为空，若为空直接返回nums2[j]; 否则返回nums1[i] 和 nums2[j]中的较小值。 当nums1的所有元素都被排序时， 其i 值等于其序列长度， 此时只需返回nums2中从下标j开始的第k个数即可。 若一般情况下，就比较上图分析的两种情况， 注意由于nums1的序列长度较短, 故 i + k / 2有可能超过nums1的最大长度。 故这里 i + k/ 2 和 nums1.size()要取一下较小值。 然后比较, 然后根据比较的情况更新相应的i, j 开始查找的位置还有k值。