剑指offer -- 排序

发表于 | 分类于
字数统计: 1.6k | 阅读时长 ≈ 7
《鬼灭之刃》 - 蝴蝶忍

剑指offer – 排序

剑指 Offer 40. 最小的k个数

Difficulty: 简单

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

1
2
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

1
2
输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

Solution

方法一：排序

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        vector<int> res;
        for (int i = 0; i < k; i++) {
            res.push_back(arr[i]);
        }
        return res;
    }
};

时间复杂度： $O(n\log n)$，其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。

空间复杂度： $O(\log n) $，排序所需额外的空间复杂度。

方法二：堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k, 0);
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        priority_queue<int> Q;
        for (int i = 0; i < k; ++i) {
            Q.push(arr[i]);
        }
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

**时间复杂度： **$O(n\log k)$，其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值，所以插入删除都是 $O(\log k)$ 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 $O(n\log k)$ 的时间复杂度。

**空间复杂度： **$O(k$)，因为大根堆里最多 k 个数。

剑指 Offer 41. 数据流中的中位数

Difficulty: 困难

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1：

1
2
3
4
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

1
2
3
4
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

  • 最多会对 addNum、findMedian 进行 50000 次调用。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> A;  // 大顶堆
    priority_queue<int, vector<int>, greater<int>> B; // 小顶堆
    MedianFinder() {

    }
    
    void addNum(int num) {
        if (A.size() == B.size()) {
            B.push(num);
            int temp = B.top();
            B.pop();
            A.push(temp);
        } else {
            A.push(num);
            int temp = A.top();
            A.pop();
            B.push(temp);
        }
    }
    
    double findMedian() {
        return A.size() == B.size() ?(A.top() + B.top()) / 2.0 : A.top();
    }
};

时间复杂度：

  • 查找中位数：$O(1)$
  • 添加数字：$O(\log N)$

**空间复杂度： **$O(N)$，其中 N 为数据流中的元素数量。

剑指 Offer 45. 把数组排成最小的数

Difficulty: 中等

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

1
2
输入: [10,2]
输出: "102"

示例 2:

1
2
输入: [3,30,34,5,9]
输出: "3033459"

提示:

  • 0 < nums.length <= 100

说明:

  • 输出结果可能非常大，所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> vec;
        for (const auto& num : nums) {
            vec.push_back(to_string(num));
        }
        // 排序中使用 lambda 函数
        sort(vec.begin(), vec.end(), [](const string& A, const string& B) { return A + B < B + A; } );
        string res = "";
        for (const auto& v : vec) {
            res += v;
        }
        return res;
    }
};

时间复杂度： $O(N\log N )$，其中 N 为数组长度，时间复杂度主要为排序算法时间复杂度

**空间复杂度： **$O(N)$，字符串数组额外空间

剑指 Offer 61. 扑克牌中的顺子

Difficulty: 简单

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

1
2
输入: [1,2,3,4,5]
输出: True

示例 2:

1
2
输入: [0,0,1,2,5]
输出: True

限制：

数组长度为 5

数组的数取值为 [0, 13] .

Solution

方法一：哈希集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isStraight(vector<int>& nums) {
        set<int> s;
        for (const auto& num : nums) {
            // 如果 num != 0 , 不是大小王的情况下
            if (num) {
                // 出现重复，则一定不是顺子
                if (s.find(num) != s.end()) return false;
                // 没有出现过，则插入到哈希集合中
                s.insert(num);
            }
            // 在集合非空的情况下，如果当前集合最大最小值差值 >= 5 
            // 则说明不可能形成顺子 (0 并没有被插入)
            if (!s.empty() && *s.rbegin() - *s.begin() >= 5) return false;
        }
        return true;
    }
};

时间复杂度： $O(1)$，遍历长度为 5

空间复杂度： $O(1)$，哈希集合可能的最大长度为 5

方法二：排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int joker = 0;
        // 排序数组
        sort(nums.begin(), nums.end());
        for (int i = 0; i < 4; i++) {
            // 统计大小王数量
            if (nums[i] == 0) joker++;
            // 如果重复，则不可能出现顺子
            else if (nums[i] == nums[i + 1]) return false;
        }
        // 最大牌 - 最小牌 < 5 则可构成顺子
        return nums[4] - nums[joker] < 5;
    }
};

时间复杂度： $O(1)$，遍历长度为 5，所以排序算法后时间复杂度仍然是 $O( 1)$

空间复杂度： $O(1)$，变量 joker

参考资料

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com) 官方题解



----------- 本文结束 -----------




0%