算法基础算法

自定义排序题目清单：定义 Cmp 结构体并重载 () 运算符

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

摘要: 题目汇总，自定义元素的比较方法，定义 Cmp 结构体病重载 ()，比较逻辑中可能含复杂的判断逻辑，Cmp 的实例可能持有额外状态。

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

在 C++ 中，可以直接调用 algorithm 中的函数进行排序：

1
sort(vec.begin(), vec.end())

默认情况是越小的值越排在前面，如果希望大的值排在前面，则可以像下面这样写：

1
sort(vec.begin(), vec.end(), greater<int>())

其中 greater<int>() 是仿函数。除了 sort，在 priority_queue、nth_element 中也有类似的特性。参考文章：

如果要自定义排序，则可以自行实现一个仿函数。

所谓自定义排序，就是当要排序的对象比较复杂需要自定义时，或者要排序的对象很简单但根据要求有另外的比较逻辑时，在使用语言自带的 sort 方法之前，需要先实现一个自定义的比较逻辑。

实现自定义比较逻辑一般有两种思想，一种是自定义一个比较函数，该函数输入两个对象，然后再函数内实现比较逻辑。另一种是在定义对象的类中定义或重载小于号，在其对应的方法内实现什么叫小于。

上述两种自定义比较逻辑的思想，一般来讲自定义比较函数的方法更通用，如果比较元素是基础的数值、字符，则不好重载小于号，而自定义 Cmp 结构体可以处理这种情况。自定义比较函数也有两种主流实现方法，一种是直接定义函数，另一种是定义名为 Cmp 的结构体对象，重载其 () 方法，此后用 Cmp 创建的实例 cmp 可以作为比较函数 cmp(obj1, obj2) 使用。

以上自定义比较函数的两种实现方式，一般来讲定义 Cmp 结构体并重载 () 的适用性更强，如果比较逻辑中需要额外的状态信息，可以塞进 Cmp 的实例的成员变量中，供重载的 () 中访问；如果比较逻辑中复杂的判断逻辑，也可以塞到 Cmp 内部的成员方法中，供重载的 () 调用。

自定义 Cmp 结构体并重载 () 实现自定义比较方法的这一套，C++ 的写法可以参考 C++自定义排序的比较函数：自定义Cmp结构体并重载()，可持有额外信息，Python 的写法增加了键函数这一步；可以参考 Python3自定义排序：直接定义键函数，或先定义比较函数再转换为键函数。

下面是题目清单以及备注，代码以及说明见后面。本文的代码都是在 C++ 中基于定义 Cmp 结构体并重载 () 的方式实现自定义比较。

题目 比较对象 备注
1356. 根据数字二进制下 1 的数目排序 整数 含有复杂的控制逻辑
1058. 最小化舍入误差以满足目标 浮点数 比较逻辑简单
1366. 通过投票对团队排名 字符 依赖额外状态信息，创建 cmp 实例时传入
791. 自定义字符串排序 字符 依赖额外状态信息，创建 cmp 实例时传入
1030. 距离顺序排列矩阵单元格 数组 依赖额外状态信息，创建 cmp 实例时传入
524. 通过删除字母匹配到字典里最长单词 字符串 含有复杂的控制逻辑
依赖额外状态信息，创建 cmp 实例时传入
179. 最大数 字符串 比较逻辑简单
406. 根据身高重建队列 数组 比较逻辑简单
1029. 两地调度 自定义对象 比较逻辑简单
1057. 校园自行车分配 自定义对象 比较逻辑简单
1090. 受标签影响的最大值 自定义对象 比较逻辑简单
1094. 拼车 自定义对象 比较逻辑简单
1333. 餐厅过滤器 自定义对象 比较逻辑简单

待比较元素为数值、字符

1356. 根据数字二进制下 1 的数目排序

比较对象是整数，但是比较过程涉及到复杂的判断逻辑，通过自定义 Cmp 并重载 () 的方式定义两个整数之间比大小，将判断逻辑在其中实现。

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
struct Cmp
{
    bool operator()(const int& n1, const int& n2) const
    {
        int ones1 = ones(n1);
        int ones2 = ones(n2);
        if(ones1 == ones2)
            return n1 < n2;
        return ones1 < ones2;
    }

    int ones(int x) const
    {
        int cnt = 0;
        while(x)
        {
            x = x & (x - 1);
            ++cnt;
        }
        return cnt;
    }
};

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<int> result(arr.begin(), arr.end());
        sort(result.begin(), result.end(), Cmp());
        return result;
    }
};

1058. 最小化舍入误差以满足目标

比较对象为浮点数，但有另外的比大小逻辑，新比较逻辑比较简单，直接自定义比较函数即可，这里具体使用定义 Cmp 结构体并重载 () 的方式实现。

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
49
50
struct Cmp
{
    bool operator()(const double& a, const double& b) const
    {
        return a - (int)a > b - (int)b;
    }
};

class Solution {
public:
    string minimizeError(vector<string>& prices, int target) {
        const double EPS = 1e-4;
        int n = prices.size();
        vector<double> ps(n);
        for(int i = 0; i < n; ++i)
        {
            const string &p = prices[i];
            stringstream ss;
            ss << p;
            ss >> ps[i];
        }
        int sum = 0;
        int integer = 0;
        for(double p: ps)
        {
            sum += (int)p;
            if(p - (int)p < EPS)
                ++integer;
        }
        int gap = target - sum; // 需要上取整的个数: gap
        if(gap < 0 || gap > n - integer) // 可以上取整的个数: n - integer
            return "-1";
        sort(ps.begin(), ps.end(), Cmp());
        double ans = 0.0;
        for(int i = 0; i < gap; ++i)
        {
            ans += ((int)ps[i] + 1) - ps[i];
        }
        for(int i = gap; i < n - integer; ++i)
        {
            ans += ps[i] - (int)ps[i];
        }
        stringstream ss;
        ss << setiosflags(ios::fixed) << setprecision(3);
        ss << ans;
        string result;
        ss >> result;
        return result;
    }
};

1366. 通过投票对团队排名

待比较对象为字符，通过自定义比较函数的方式实现字符间比大小，但这里比较字符 a 和 b 的大小需要依赖额外的信息。具体做法是定义 Cmp 结构体并重载 ()，同时在创建实例时将所需的额外信息传入进去，也就是让 Cmp 持有状态。

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
class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int n = votes.size();
        int m = votes[0].size();
        Cmp cmp(m);
        for(const string& vote: votes)
        {
            for(int i = 0; i < m; ++i)
                ++cmp.polls[vote[i] - 'A'][i];
        }
        string result = votes[0];
        sort(result.begin(), result.end(), cmp);
        return result;
    }

private:
    struct Cmp
    {
        vector<vector<int> > polls;
        Cmp(int m)
        {
            polls = vector<vector<int> >(26, vector<int>(m, 0));
        }
        bool operator()(const char& a, const char& b)
        {
            for(int i = 0; i < (int)polls[0].size(); ++i)
            {
                if(polls[a - 'A'][i] > polls[b - 'A'][i])
                    return true;
                else if(polls[a - 'A'][i] < polls[b - 'A'][i])
                    return false;
            }
            return a < b;
        }
    };
};

791. 自定义字符串排序

待比较对象为字符，通过自定义比较函数的方式实现字符间比大小，具体做法是定义 Cmp 类并重载 () 函数，其中 Cmp 持有状态。

参考题解：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
class Solution {
public:
    string customSortString(string S, string T) {
        int n = S.size();
        if(n <= 1) return T;
        vector<int> char_idx(26, -1);
        for(int i = 0; i < n; ++i)
            char_idx[S[i] - 'a'] = i;
        Dictionary_less dictionary_less(char_idx);
        sort(T.begin(), T.end(), dictionary_less);
        return T;
    }

private:
    struct Dictionary_less
    {
        vector<int> char_idx;
        Dictionary_less(vector<int> mapping):char_idx(mapping) {}
        bool operator() (const char& c1, const char& c2)
        {
            return char_idx[c1 - 'a'] < char_idx[c2 - 'a'];
        }
    };
};

待比较元素为整数数组、字符串

1030. 距离顺序排列矩阵单元格

待比较的对象为数组 vector<int>，通过自定义比较函数的范式实现排序，具体做法是在 C++ 中定义 Cmp 类并重载 () 运算符。但注意这里的 Cmp 中持有状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Cmp
{
    int r0, c0;
    Cmp(int r0, int c0):r0(r0),c0(c0){}
    bool operator()(const vector<int>& p1, const vector<int>& p2) const
    {
        return abs(p1[0] - r0) + abs(p1[1] - c0) < abs(p2[0] - r0) + abs(p2[1] - c0);
    }
};

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
        vector<vector<int>> result;
        for(int i = 0; i < R; ++i)
            for(int j = 0; j < C; ++j)
                result.push_back({i, j});
        sort(result.begin(), result.end(), Cmp(r0, c0));
        return result;
    }
};

524. 通过删除字母匹配到字典里最长单词

待比较对象为字符串 string, 通过自定义比较函数实现字符串之间比大小，在取最大元素 max_element 函数中使用。

具体做法是在 C++ 中定义 Cmp 类并重载 () 运算符。但注意这里的 Cmp 中持有状态，并且比较过程中有复杂的判断逻辑。

参考题解：力扣524-通过删除字母匹配到字典里最长单词。

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
struct Cmp
{
    string origin;
    Cmp(const string& origin):origin(origin){}
    bool operator()(const string& word1, const string& word2) const
    {
        bool flag1 = check(word1), flag2 = check(word2);
        if(!flag2) return false;
        if(!flag1) return true;
        if(word1.size() == word2.size())
            return word1 > word2;
        return word1.size() < word2.size();
    }
    bool check(const string& word) const
    {
        // word 是否可以通过 origin 删除某些字符得到
        int n = origin.size();
        int m = word.size();
        if(m > n) return false;
        int i = 0, j = 0;
        while(i < n && j < m)
        {
            if(origin[i] == word[j])
                ++j;
            ++i;
            if(m - j > n - i)
                return false;
        }
        return j == m;
    }
};

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        if(s.empty() || d.empty()) return "";
        Cmp cmp(s);
        auto it = max_element(d.begin(), d.end(), cmp);
        if(cmp.check(*it))
            return *it;
        return "";
    }
};

179. 最大数

待比较对象为字符串，比较逻辑比较简单，在 C++ 中直接定义一个比较函数或定义结构体然后重载 () 均可，这里直接定义函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        if(nums.empty()) return "";
        int n = nums.size();
        if(n == 1) return to_string(nums[0]);
        vector<string> nums_str(n, "");
        for(int i = 0; i < n; ++i)
            nums_str[i] = to_string(nums[i]);
        sort(nums_str.begin(), nums_str.end(), dictionary_order_greater);
        if(nums_str[0] == "0") return "0";
        string result = "";
        for(string item: nums_str)
            result += item;
        return result;
    }

private:
    static bool dictionary_order_greater(const string& s1, const string& s2)
    {
        return s1 + s2 > s2 + s1;
    }
};

406. 根据身高重建队列

待比较对象为数组 vector<int>，比较逻辑比较简单，在 C++ 中直接定义一个比较函数或定义结构体然后重载 () 均可，这里定义结构体并重载 ()。

先排序再插入，排序 $O(N\log N)$，插入 $O(N^{2})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        if(people.empty()) return vector<vector<int> >();
        int n = people.size();
        sort(people.begin(), people.end(), Cmp());
        vector<vector<int> > result;
        for(int i = 0; i < n; ++i)
            result.insert(result.begin() + people[i][1], people[i]);
        return result;
    }

private:
    struct Cmp
    {
        bool operator()(const vector<int>& vec1, const vector<int>& vec2)
        {
            if(vec1[0] == vec2[0])
                return vec1[1] < vec2[1];
            return vec1[0] > vec2[0];
        }
    };
};

待比较元素为自定义对象

1029. 两地调度

待比较元素为自定义对象。比较逻辑简单，自定义比较函数即可。这里的做法是定义 Cmp 结构体并重载 ()。

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
struct Person
{
    int a, b;
    Person(int a, int b):a(a),b(b){}
};

struct Cmp
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        return (p1.a - p1.b) < (p2.a - p2.b);
    }
};

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<Person> persons;
        for(int i = 0; i < n; ++i)
        {
            persons.push_back(Person(costs[i][0], costs[i][1]));
        }
        sort(persons.begin(), persons.end(), Cmp());
        int ans = 0;
        for(int i = 0; i < n / 2; ++i)
            ans += persons[i].a;
        for(int i = n / 2; i < n; ++i)
            ans += persons[i].b;
        return ans;
    }
};

1057. 校园自行车分配

待比较对象是自定义对象。通过自定义比较函数实现排序，具体做法是在 C++ 中定义 Cmp 类并重载 () 运算符。

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
struct Pair
{
    int x1, y1, x2, y2;
    int d;
    int id1, id2;
    Pair(int x1, int y1, int x2, int y2, int id1, int id2):x1(x1),y1(y1),x2(x2),y2(y2),id1(id1),id2(id2)
    {
        d = abs(x1 - x2) + abs(y1 - y2);
    }
};

struct Cmp
{
    bool operator()(const Pair& p1, const Pair& p2) const
    {
        if(p1.d == p2.d)
        {
            if(p1.id1 == p2.id1)
                return p1.id2 < p2.id2;
            return p1.id1 < p2.id1;
        }
        return p1.d < p2.d;
    }
};

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int n = workers.size(), m = bikes.size();
        vector<bool> used1(n, false), used2(m, false);
        vector<Pair> pairs;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                pairs.emplace_back(workers[i][0], workers[i][1], bikes[j][0], bikes[j][1], i, j);
        sort(pairs.begin(), pairs.end(), Cmp());
        vector<int> result(n, -1);
        for(const Pair& p: pairs)
        {
            if(used1[p.id1] || used2[p.id2])
                continue;
            result[p.id1] = p.id2;
            used1[p.id1] = true;
            used2[p.id2] = true;
        }
        return result;
    }
};

1090. 受标签影响的最大值

待比较对象为自定义对象，通过自定义比较函数的方式实现比大小，具体做法是定义结构体 Cmp 并重载 ()。

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
struct Item
{
    int val;
    int label;
    Item(int v, int l):val(v),label(l){}
    Item():val(-1),label(-1){}
};

struct Cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.val > i2.val;
    }
};

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        int n = values.size();
        vector<Item> items(n);
        int max_label = -1;
        for(int i = 0; i < n; ++i)
        {
            items[i].val = values[i];
            items[i].label = labels[i];
            max_label = max(max_label, labels[i]);
        }
        vector<int> labels_record(max_label + 1, use_limit);
        sort(items.begin(), items.end(), Cmp());
        int cnt = 0;
        int ans = 0;
        for(const Item& i: items)
        {
            if(labels_record[i.label] == 0)
                continue;
            ans += i.val;
            ++cnt;
            --labels_record[i.label];
            if(cnt == num_wanted)
                break;
        }
        return ans;
    }
};

1094. 拼车

比较元素为自定义对象，但有另外的比大小逻辑，新比较逻辑比较简单，直接自定义比较函数即可，这里具体使用定义 Cmp 结构体并重载 () 的方式实现。

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
struct Event
{
    int idx;
    // 右端点排前面，先下
    bool side; // false: 右，true: 左
    int num; // 涉及的乘客数，根据 side 决定是上还是下
    Event(int idx, bool side, int num):idx(idx),side(side),num(num){}
};

struct Cmp
{
    bool operator()(const Event& e1, const Event& e2) const
    {
        if(e1.idx == e2.idx)
            return e1.side < e2.side;
        return e1.idx < e2.idx;
    }
};

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<Event> events;
        for(const vector<int>& trip: trips)
        {
            // trip[0,1,2] : num, start, end
            events.push_back(Event(trip[1], true, trip[0]));
            events.push_back(Event(trip[2], false, trip[0]));
        }
        sort(events.begin(), events.end(), Cmp());
        int sum = 0;
        for(const Event &e : events)
        {
            if(e.side)
                sum += e.num;
            else
                sum -= e.num;
            if(sum > capacity)
                return false;
        }
        return true;
    }
};

1333. 餐厅过滤器

比较对象是自定义对象。通过自定义比较函数实现排序，具体做法是在 C++ 中定义 Cmp 类并重载 () 运算符。

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
struct Restaurant
{
    int id, rate;
    Restaurant(int id, int rate):id(id),rate(rate){}
};

struct Cmp
{
    bool operator()(const Restaurant& r1, const Restaurant& r2) const
    {
        if(r1.rate == r2.rate)
            return r1.id > r2.id;
        return r1.rate > r2.rate;
    }
};

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        vector<Restaurant> vec;
        for(const vector<int> &item: restaurants)
        {
            if(veganFriendly == 1 && item[2] == 0)
                continue;
            if(item[3] > maxPrice)
                continue;
            if(item[4] > maxDistance)
                continue;
            vec.emplace_back(item[0], item[1]);
        }
        sort(vec.begin(), vec.end(), Cmp());
        int m = vec.size();
        vector<int> result(m);
        for(int i = 0; i < m; ++i)
            result[i] = vec[i].id;
        return result;
    }
};
Share