自定义排序

  |  

$1 自定义排序

$1.1 791. 自定义字符串排序

S 串只含字母 a-z(最长26),我们要找到的是这26个字母的大小关系。26个字母的大小关系可以通过权重表示,权重越小,该字母在字符串排序后的位置约靠前。而 S 串通过字母的位置告诉了我们一些字母的权重,即:把出现过的字母在S中的下标视为该字母的权重。所以可以用一个长度 26 的 vector 保存 26 个字母的权重,值初始化为 -1,遍历 S,对 S 中的每一个字母将其下标赋值给 vector 的相应位置,这样就得到了从 S 串可以得到的部分字母的权重,权重关系就对应了字母的大小关系。

C++ 中通过给 sort 函数传入自定义的比较函数,可以实现自定义的排序。但是这里的排序需要查遍历 S 串得到的 vector,常用的直接写比较函数的方法不好实现。

还有一种方法是写一个结构体,结构体内部可以持有一个 vector 成员变量,通过初始化的方式将遍历 S 串得到的 vector 传给结构体的对象。重载该结构体的 (),该结构体创建的对象可以当做函数使用,且内部已经持有了遍历 S 得到的 vector。

即:在 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
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'];
}
};
};

$1.2 1329. 将矩阵按对角线排序

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
class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
vector<int> cand;
vector<vector<int>> result(n, vector<int>(m, -1));
for(int k = -(n - 1); k <= m - 1; ++k)
{
// k = j - i
cand.clear();
for(int i = max(0, -k); i <= min(n - 1, m - 1 - k); ++i)
{
int j = i + k;
cand.push_back(mat[i][j]);
}
sort(cand.begin(), cand.end());
int iter = 0;
for(int i = max(0, -k); i <= min(n - 1, m - 1 - k); ++i)
{
int j = i + k;
result[i][j] = cand[iter++];
}
}
return result;
}
};

$1.3 1333. 餐厅过滤器

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;
}
};

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

在 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;
}
};

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

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 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 "";
}
};

$1.6 179. 最大数

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;
}
};

$1.7 406. 根据身高重建队列

先排序再插入,排序 $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];
}
};
};

2.8 1366. 通过投票对团队排名

持有状态的自定义排序

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;
}
};
};

2.9 1057. 校园自行车分配

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;
}
};

2.10 1029. 两地调度

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;
}
};

2.11 1094. 拼车

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;
}
};

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

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;
}
};

2.13 1090. 受标签影响的最大值

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;
}
};

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

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;
}
};

Share