编程C++

【STL】字典序比较 lexicographical_compare

字数统计: 974字   |   阅读时长: 4分
, ,

摘要: 本文介绍在 C++ STL 中的字典序比较方法 lexicographical_compare

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文介绍在 C++ STL 中的字典序比较方法 lexicographical_compare，然后该组件来解决力扣第 321 题。

lexicographical_compare

原型

1
2
3
4
5
6
7
8
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                Compare comp);

返回 [first1, last1) 是否字典序小于 [first2, last2)，可以自定义比较方法 Comp，如果没有自定义比较方法，则 [first, last) 中的元素需要定义了 <

实现

1
2
3
4
5
6
7
8
9
10
while(first1 != last1)
{
    if(first2 == last2 || *first2 < *first1) 
        return false;
    else if(*first1 < *first2) 
        return true;
    ++first1; 
    ++first2;
}
return(first2 != last2);

使用

当需要比较两个字符串或者两个数组的字典序时，可以直接调用

1
2
3
4
5
if(lexicographical_compare(str1.begin(), str1.end(), str2.begin(), str2.end()))
    ...

if(lexicographical_compare(nums1.begin(), nums1.end(), nums2.begin(), nums2.end()))
    ...

例题

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]

示例 2:
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]

示例 3:
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]

算法：贪心

考虑从一个数组 nums 中取 k 个数使得所得的数最大，可以用贪心算法，类似于 402. 移掉K位数字。如果函数 solve(nums, k) 返回从 nums 中取出的使得所得数最大的 k 位数字，它的算法流程大致如下：

1
2
从前向后枚举数字，当前枚举到 cur，用一个栈存储当前数字之前的数字：
    若 cur < 栈顶：则不断出栈直至 cur < 栈顶不成立，或者栈空，或者已经删除了 k 个

当有两个数组 nums1 和 nums2 时，可以直接复用 solve(nums, k) 从 nums1 取 k1 个，形成结果 vec1，从 nums2 取 k2 个，形成结果 vec2，然后合并到一起。

合并的过程需要比较 vec1 和 vec2 的字典序，可以直接用 lexicographical_compare。

算法如下：

1
2
3
4
5
6
7
枚举 `k1 + k2 = k`
对于每个 k1, k2，求两次单数组取 k 个数形成最大数的结果 vec1 和 vec2
    vec1 = solve(nums1, k1);
    vec2 = solve(nums2, k2);
    merge(vec1, vec2)

类似分治的思想

代码 (C++)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> result;
        int n1 = nums1.size(), n2 = nums2.size();
        for(int k1 = 0; k1 <= k; ++k1)
        {
            int k2 = k - k1;
            if(k1 > n1 || k2 > n2)
                continue;
            result = max(result, merge(solve(nums1, k1), solve(nums2, k2)));
        }
        return result;
    }

private:
    vector<int> solve(const vector<int>& nums, int k)
    {
        if(k == 0) return {};
        vector<int> result;
        int n = nums.size();
        int k_delete = n - k;
        for(int i = 0; i < n; ++i)
        {
            while(!result.empty() && result.back() < nums[i] && k_delete > 0)
            {
                result.pop_back();
                --k_delete;
            }
            result.push_back(nums[i]);
        }
        // 取前 k 个
        result.resize(k);
        return result;
    }

    vector<int> merge(const vector<int>& vec1, const vector<int>& vec2)
    {
        vector<int> result;
        auto s1 = vec1.cbegin();
        auto e1 = vec1.cend();
        auto s2 = vec2.cbegin();
        auto e2 = vec2.cend();
        while(s1 != e1 || s2 != e2)
            result.push_back(lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++);
        return result;
    }
};
Share