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
,请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同,请你按照数值本身将它们 降序 排序。
请你返回排序后的数组。
思路
按着题目的要求,先算出数组 n u m s 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 n n 名粉丝,编号从 1 1 1 到 n n n,但她只能选择其中 k k k 名送礼物。为了公平起见,她决定选择其中对她支持力度最大的前 k k k 名粉丝。如果有两名粉丝的支持力度相同,则优先选择点赞数更多的粉丝;如果点赞数也相同,则优先选择编号更小的粉丝(因为这意味着Ta关注K小姐的时间更早)。
每名粉丝如果给K小姐点一次赞,则对K小姐的支持力度就增加 1 1 1 点;如果收藏K小姐的一篇文章,则对K小姐的支持力度增加 2 2 2 点。
现在K小姐想知道,她应该选择哪 k k k 名粉丝送出礼物,你能帮帮她吗?
输入格式
输入包含 n + 1 n+1 n+1 行。
第一行包含两个正整数 n , k ( 1 ≤ k ≤ n ≤ 1 0 5 ) n,k\ (1 \leq k \leq n \leq 10^5) n,k (1≤k≤n≤105),分别表示对K小姐有过支持的粉丝个数,以及K小姐选择送礼的粉丝个数。
接下来 n n n 行,每行两个整数 x , y ( 0 ≤ x , y ≤ 1 0 5 ) x,y\ (0 \leq x,y \leq 10^5) x,y (0≤x,y≤105),表示第 i i i 位粉丝给K小姐点过 x x x 次赞,收藏过 y y y 个K小姐的文章。
输出格式
输出包含一行 k k k 个正整数,表示K小姐选择出送礼物的粉丝们的编号。(按照升序输出)
样例输入
4 2
1 2
2 1
3 0
1 3
样例输出
1 4
数据范围
- 1 ≤ k ≤ n ≤ 1 0 5 1 \leq k \leq n \leq 10^5 1≤k≤n≤105
- 0 ≤ x , y ≤ 1 0 5 0 \leq x,y \leq 10^5 0≤x,y≤105
题解
本题可以按照题目描述,直接进行模拟。
-
将每个粉丝的信息(点赞数、收藏数、编号)存储在一个数组中。
-
定义一个自定义的排序规则:
- 首先比较支持力度(点赞数 + 收藏数 * 2)
- 如果支持力度相同,则比较收藏数
- 如果收藏数也相同,则比较编号
-
对存储粉丝信息的数组自定义的排序规则进行排序。
-
取排序后的前 k k k 个粉丝的编号,按照升序输出即可。
时间复杂度为 O ( n log n ) O(n \log n) O(nlogn),空间复杂度为 O ( n ) O(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 元 ) |
🎀 其中笔试真题选自近 一年半 互联网春秋招的笔试题