Day01-自定排序

前言

给大家推荐一下咱们的 陪伴打卡小屋 知识星球啦，详细介绍 =>笔试刷题陪伴小屋-打卡赢价值丰厚奖励 <=

⏰小屋将在每日上午发放打卡题目，包括：

• 一道该算法的模版题 (主要以力扣，牛客，acwing等其他OJ网站的题目作为模版)
• 该算法的应用题（主要以往期互联网大厂 笔试真题 的形式出现，评测在咱们的 笔试突围OJ）

小屋day01

自定义排序 在笔试中很少会单独考，但是应用非常广泛，一般是作为中间的流程出现，建议小伙伴们要好好掌握哦。

✨ 自定义排序模版

对于排序规则，这里采用 lambda 表达式的简洁写法。

Java

在Java中，lambda表达式用于简化Comparator接口的实现，从而实现自定义排序。Java 8引入了lambda表达式，使得代码更加简洁。以下是一个示例，展示如何使用lambda表达式对自定义对象进行排序：

List<Student> studentList = new ArrayList<>();
studentList.add(new Student("Jon", 22, 1001));
studentList.add(new Student("Steve", 19, 1003));

// 按名字排序
studentList.sort((Student s1, Student s2) -> s1.getName().compareTo(s2.getName()));

// 按年龄排序
studentList.sort((Student s1, Student s2) -> Integer.compare(s1.getAge(), s2.getAge()));

C++

在C++中，lambda表达式可以用来定义自定义排序规则。C++11引入了lambda表达式，使得代码更加简洁和灵活。以下是一个示例，展示如何使用lambda表达式对字符串向量按长度进行排序：

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<std::string> strings = {"apple", "banana", "cherry", "dog", "elephant"};
    std::sort(strings.begin(), strings.end(), [](const std::string& a, const std::string& b) {
        return a.length() < b.length();
    });
    for (const auto& s : strings) {
        std::cout << s << std::endl;
    }
    return 0;
}

Python

在Python中，lambda表达式常用于sorted函数和sort方法的key参数，以实现自定义排序。以下是一个示例，展示如何使用lambda表达式对字符串列表按长度进行排序：

words = ["apple", "banana", "cherry", "date", "elderberry"]
sorted_words = sorted(words, key=lambda x: len(x))
print(sorted_words)

🫔 模版题

leetcode-1636. 按照频率将数组升序排序
评测链接🔗 https://leetcode.cn/problems/sort-array-by-increasing-frequency/)

题目描述

给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。

请你返回排序后的数组。

---

思路

按着题目的要求，先算出数组 $nums$ 中各元素的频率，然后按照元素频率和数值对数组进行排序即可。

对于排序规则，这里采用 lambda 表达式的简洁写法。

• Python

  class Solution:
      def frequencySort(self, nums: List[int]) -> List[int]:
          cnt = Counter(nums) # 计数器
          nums.sort(key=lambda x: (cnt[x], -x)) # 默认从小到大排序
          return nums
  

• C++

  class Solution {
  public:
      vector<int> frequencySort(vector<int>& nums) {
          vector<int> cnt(201); // 计数器
          for (int v : nums) {
              ++cnt[v + 100];
          }
        // 也可以写成二元组的形式
        // nums[i] = {cnt[x], -x};
        // 然后从小到大排序
          sort(nums.begin(), nums.end(), [&](const int a, const int b) {
              if (cnt[a + 100] == cnt[b + 100]) return a > b;
              return cnt[a + 100] < cnt[b + 100];
          });
          return nums;
      }
  };
  

• Java

  class Solution {
      public int[] frequencySort(int[] nums) {
          List<Integer> list = new ArrayList<>();
          Map<Integer, Integer> freqs = new HashMap<>(); // 计数器
          for (int x : nums) {
              list.add(x);
              freqs.put(x, freqs.getOrDefault(x, 0) + 1);
          }
          Collections.sort(list, (a, b) -> { // Java的自定义排序
              int freq1 = freqs.get(a), freq2 = freqs.get(b);
              return freq1 == freq2 ? b - a : freq1 - freq2;
          });
          for (int i = 0; i < nums.length; ++i) {
              nums[i] = list.get(i);
          }
          return nums;
      }
  }
  

🍰 笔试真题

• 该题来自今年小红书春招的笔试题，题目难度为 easy，考查的是比较裸的自定义排序。

• 另外给大家带来一道进阶版的，今年华为春招的笔试题，这边给大家放出评测链接，有能力的小伙伴可以去试一试哦

  进阶版🔗评测链接：https://app5938.acapp.acwing.com.cn/problem/HW001

盛夏送礼物

评测链接：https://app5938.acapp.acwing.com.cn/contest/3/problem/Day01

题目描述

K小姐是一名知名博主，她在某个盛夏的午后决定给她的粉丝送一些小礼物。她有 $n$ 名粉丝,编号从 $1$ 到 $n$，但她只能选择其中 $k$ 名送礼物。为了公平起见，她决定选择其中对她支持力度最大的前 $k$ 名粉丝。如果有两名粉丝的支持力度相同，则优先选择点赞数更多的粉丝；如果点赞数也相同，则优先选择编号更小的粉丝(因为这意味着Ta关注K小姐的时间更早)。

每名粉丝如果给K小姐点一次赞，则对K小姐的支持力度就增加 $1$ 点；如果收藏K小姐的一篇文章，则对K小姐的支持力度增加 $2$ 点。

现在K小姐想知道，她应该选择哪 $k$ 名粉丝送出礼物，你能帮帮她吗?

输入格式

输入包含 $n+1$ 行。

第一行包含两个正整数 $n,k(1\le k\le n\le 10^5)$,分别表示对K小姐有过支持的粉丝个数,以及K小姐选择送礼的粉丝个数。

接下来 $n$ 行,每行两个整数 $x,y(0\le x,y\le 10^5)$,表示第 $i$ 位粉丝给K小姐点过 $x$ 次赞,收藏过 $y$ 个K小姐的文章。

输出格式

输出包含一行 $k$ 个正整数,表示K小姐选择出送礼物的粉丝们的编号。(按照升序输出)

样例输入

4 2
1 2
2 1
3 0
1 3

样例输出

1 4

数据范围

• $1\le k\le n\le 10^5$
• $0\le x,y\le 10^5$

---

题解

本题可以按照题目描述,直接进行模拟。

1. 将每个粉丝的信息(点赞数、收藏数、编号)存储在一个数组中。

2. 定义一个自定义的排序规则:

   • 首先比较支持力度(点赞数 + 收藏数 * 2)
   • 如果支持力度相同,则比较收藏数
   • 如果收藏数也相同,则比较编号

3. 对存储粉丝信息的数组自定义的排序规则进行排序。

4. 取排序后的前 $k$ 个粉丝的编号,按照升序输出即可。

时间复杂度为 $O(n\log n)$,空间复杂度为 $O(n)$。

参考代码

• Python

n, k = map(int, input().split())
fans = []
for i in range(n):
    x, y = map(int, input().split())
    fans.append((x, y, i + 1))

fans.sort(key=lambda x: (-x[0] - x[1] * 2, -x[1], x[2]))

res = [fans[i][2] for i in range(k)]
res.sort()
print(*res)

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] fans = new int[n][3];
        for (int i = 0; i < n; i++) {
            fans[i][0] = sc.nextInt();
            fans[i][1] = sc.nextInt();
            fans[i][2] = i + 1;
        }

        Arrays.sort(fans, (a, b) -> {
            int wa = a[0] + a[1] * 2;
            int wb = b[0] + b[1] * 2;
            if (wa != wb) {
                return wb - wa;
            } else if (a[1] != b[1]) {
                return b[1] - a[1];
            } else {
                return a[2] - b[2];
            }
        });

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = fans[i][2];
        }
        Arrays.sort(res);
        for (int i = 0; i < k; i++) {
            System.out.print(res[i]);
            System.out.print(' ');
        }
    }
}

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> fans(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cin >> fans[i][0] >> fans[i][1];
        fans[i][2] = i + 1;
    }

    sort(fans.begin(), fans.end(), [](const vector<int>& a, const vector<int>& b) {
        int wa = a[0] + a[1] * 2;
        int wb = b[0] + b[1] * 2;
        if (wa != wb) {
            return wa > wb;
        } else if (a[1] != b[1]) {
            return a[1] > b[1];
        } else {
            return a[2] < b[2];
        }
    });

    vector<int> res(k);
    for (int i = 0; i < k; i++) {
        res[i] = fans[i][2];
    }
    sort(res.begin(), res.end());
    for (int i = 0; i < k; i++) {
        cout << res[i] << " ";
    }

    return 0;
}

秋招笔试刷题陪伴小屋

🍰 打卡奖励预览

打卡时长	奖励内容
7天	任选一家最新互联网笔试真题 x 1 (价值 29.9 元)
14天	任选一家最新互联网笔试真题 x 3 + 笔试面试经验贴
21天	任选一家最新互联网笔试真题 x 5 + 清隆三语言算法模版
28天	最新互联网大厂笔试真题汇总(价值 199 元) + 华为OD机试训练营 (价值 89 元 )

🎀 其中笔试真题选自近 一年半 互联网春秋招的笔试题