Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit307293d

Browse files
committed
Added3478-choose-k-elements-with-maximum-sum.md with Python solution.
1 parentcd5daa6 commit307293d

File tree

2 files changed

+262
-0
lines changed

2 files changed

+262
-0
lines changed
Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
Original link:[coding5.com - Best practices of LeetCode solutions](https://coding5.com/en/leetcode/3478-choose-k-elements-with-maximum-sum)
2+
3+
#3478. Choose K Elements With Maximum Sum - Best practices of LeetCode solutions
4+
5+
LeetCode link:[3478. Choose K Elements With Maximum Sum](https://leetcode.com/problems/choose-k-elements-with-maximum-sum), Difficulty:**Medium**.
6+
7+
##LeetCode description of "3478. Choose K Elements With Maximum Sum"
8+
9+
You are given two integer arrays,`nums1` and`nums2`, both of length`n`, along with a positive integer`k`.
10+
11+
For each index`i` from`0` to`n - 1`, perform the following:
12+
13+
- Find all indices`j` where`nums1[j]` is less than`nums1[i]`.
14+
- Choose at most`k` values of`nums2[j]` at these indices to maximize the total sum.
15+
16+
Return an array`answer` of size`n`, where`answer[i]` represents the result for the corresponding index`i`.
17+
18+
###[Example 1]
19+
20+
**Input**:`nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2`
21+
22+
**Output**:`[80,30,0,80,50]`
23+
24+
**Explanation**:
25+
26+
```
27+
- For `i = 0`: Select the 2 largest values from `nums2` at indices `[1, 2, 4]` where `nums1[j] < nums1[0]`, resulting in `50 + 30 = 80`.
28+
- For `i = 1`: Select the 2 largest values from `nums2` at index `[2]` where `nums1[j] < nums1[1]`, resulting in `30`.
29+
- For `i = 2`: No indices satisfy `nums1[j] < nums1[2]`, resulting in `0`.
30+
- For `i = 3`: Select the 2 largest values from `nums2` at indices `[0, 1, 2, 4]` where `nums1[j] < nums1[3]`, resulting in `50 + 30 = 80`.
31+
- For `i = 4`: Select the 2 largest values from `nums2` at indices `[1, 2]` where `nums1[j] < nums1[4]`, resulting in `30 + 20 = 50`.
32+
```
33+
34+
###[Example 2]
35+
36+
**Input**:`nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1`
37+
38+
**Output**:`[0,0,0,0]`
39+
40+
**Explanation**:
41+
42+
```
43+
Since all elements in `nums1` are equal, no indices satisfy the condition `nums1[j] < nums1[i]` for any `i`, resulting in `0` for all positions.
44+
```
45+
46+
###[Constraints]
47+
48+
-`n == nums1.length == nums2.length`
49+
-`1 <= n <= 10^5`
50+
-`1 <= nums1[i], nums2[i] <= 10^6`
51+
-`1 <= k <= n`
52+
53+
###[Hints]
54+
55+
<details>
56+
<summary>Hint 1</summary>
57+
Sort`nums1` and its corresponding`nums2` values together based on`nums1`.
58+
59+
60+
</details>
61+
62+
<details>
63+
<summary>Hint 2</summary>
64+
Use a max heap to track the top`k` values of`nums2` as you process each element in the sorted order.
65+
66+
67+
</details>
68+
69+
##Intuition
70+
71+
* Seeing this, everyone will definitely think of sorting`nums1` from small to large, so that the front is less than or equal to the back, but the indexes will be**messy** when sorting. If there is no good way to solve this problem, the whole question cannot be solved. Please think about it first.
72+
73+
ddd Bring the`index` when sorting, that is, the object to be sorted is an array of tuples of`(num, index)`. This technique**must be mastered**, as it will be used in many questions.ddd
74+
75+
After solving the above problems, the indexes are all there, let's continue reading:
76+
77+
* Requirement 2: Choose at most`k` values of`nums2[j]` at these indices to**maximize** the total sum.
78+
79+
After seeing this, have you thought of any good method?
80+
81+
ddd Heap sort, maintain a large root heap of size`k`. This is also a knowledge point that is often tested,**must be mastered**. ddd
82+
83+
Seeing this, please implement the code according to the above prompts.
84+
85+
* Finally, it is found that the repeated`num` that appear continuously should be specially processed, that is, the values ​​in`answer` corresponding to the same`num` should be the same. There are many ways to deal with it. What is the simplest way to deal with it?
86+
87+
ddd Use a`Map`,`key` is`num`, and the same`key` directly uses the`value` corresponding to`key`. ddd
88+
89+
##Complexity
90+
91+
- Time complexity:`O(N * logN)`.
92+
- Space complexity:`O(N)`.
93+
94+
##Python
95+
96+
```python
97+
classSolution:
98+
deffindMaxSum(self,nums1: List[int],nums2: List[int],k:int) -> List[int]:
99+
num_index_list= [(num, index)for index, numinenumerate(nums1)]# key 1
100+
num_index_list.sort()
101+
102+
answer= [None]*len(nums1)
103+
k_max_nums= []
104+
sum_=0
105+
num_to_sum= defaultdict(int)# key 2
106+
107+
for i, num_indexinenumerate(num_index_list):
108+
num, index= num_index
109+
110+
if numin num_to_sum:
111+
answer[index]= num_to_sum[num]
112+
else:
113+
answer[index]= sum_
114+
num_to_sum[num]= sum_
115+
116+
heapq.heappush(k_max_nums, nums2[index])
117+
sum_+= nums2[index]
118+
119+
iflen(k_max_nums)> k:
120+
num= heapq.heappop(k_max_nums)# key 3
121+
sum_-= num
122+
123+
return answer
124+
```
125+
126+
##Other languages
127+
128+
```java
129+
// Welcome to create a PR to complete the code of this language, thanks!
130+
```
Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
原文链接：[coding5.com - 力扣题解最佳实践](https://coding5.com/zh/leetcode/3478-choose-k-elements-with-maximum-sum)
2+
3+
#3478. 选出和最大的 K 个元素 - 力扣题解最佳实践
4+
5+
力扣链接：[3478. 选出和最大的 K 个元素](https://leetcode.cn/problems/choose-k-elements-with-maximum-sum), 难度：**中等**。
6+
7+
##力扣“3478. 选出和最大的 K 个元素”问题描述
8+
9+
给你两个整数数组，`nums1` 和`nums2`，长度均为`n`，以及一个正整数`k` 。
10+
11+
对从`0` 到`n - 1` 每个下标`i` ，执行下述操作：
12+
13+
- 找出所有满足`nums1[j]` 小于`nums1[i]` 的下标`j` 。
14+
- 从这些下标对应的`nums2[j]` 中选出 至多`k` 个，并 最大化 这些值的总和作为结果。
15+
16+
返回一个长度为`n` 的数组`answer` ，其中`answer[i]` 表示对应下标`i` 的结果。
17+
18+
19+
###[示例 1]
20+
21+
**输入**:`nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2`
22+
23+
**输出**:`[80,30,0,80,50]`
24+
25+
**解释**:
26+
27+
```
28+
- 对于 `i = 0` ：满足 `nums1[j] < nums1[0]` 的下标为 `[1, 2, 4]` ，选出其中值最大的两个，结果为 `50 + 30 = 80` 。
29+
- 对于 `i = 1` ：满足 `nums1[j] < nums1[1]` 的下标为 `[2]` ，只能选择这个值，结果为 `30` 。
30+
- 对于 `i = 2` ：不存在满足 `nums1[j] < nums1[2]` 的下标，结果为 `0` 。
31+
- 对于 `i = 3` ：满足 `nums1[j] < nums1[3]` 的下标为 `[0, 1, 2, 4]` ，选出其中值最大的两个，结果为 `50 + 30 = 80` 。
32+
- 对于 `i = 4` ：满足 `nums1[j] < nums1[4]` 的下标为 `[1, 2]` ，选出其中值最大的两个，结果为 `30 + 20 = 50` 。
33+
```
34+
35+
###[示例 2]
36+
37+
**输入**:`nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1`
38+
39+
**输出**:`[0,0,0,0]`
40+
41+
**解释**:
42+
43+
```
44+
由于 `nums1` 中的所有元素相等，不存在满足条件 `nums1[j] < nums1[i]`，所有位置的结果都是 `0` 。
45+
```
46+
47+
###[约束]
48+
49+
-`n == nums1.length == nums2.length`
50+
-`1 <= n <= 10^5`
51+
-`1 <= nums1[i], nums2[i] <= 10^6`
52+
-`1 <= k <= n`
53+
54+
###[Hints]
55+
56+
<details>
57+
<summary>提示 1</summary>
58+
Sort`nums1` and its corresponding`nums2` values together based on`nums1`.
59+
60+
61+
</details>
62+
63+
<details>
64+
<summary>提示 2</summary>
65+
Use a max heap to track the top`k` values of`nums2` as you process each element in the sorted order.
66+
67+
68+
</details>
69+
70+
##思路
71+
72+
- 要求1：找出所有满足`nums1[j]` 小于`nums1[i]` 的下标`j` 。
73+
看到这个，大家一定会想到把`nums1` 按从小到大排序，这样，前面的小于等于后面的，但一排序下标就**乱**了。如果对这个问题没有好办法解决，整个题目就做不出来。先请思考下。
74+
75+
ddd在排序时带上索引下标，即排序的对象是元组`(num, index)`的数组。这个技术**一定要掌握**，许多题目都会用到。ddd
76+
77+
解决了上面的问题，下标就都有了，我们再看：
78+
79+
- 要求2：从这些下标对应的`nums2[j]` 中选出 至多`k` 个，并**最大化** 这些值的总和作为结果。
80+
81+
看到这个，你想到用什么好方法了吗？
82+
83+
ddd堆排序，维护一个大小为`k` 的大根堆。这也是经常考察的知识点，**一定要掌握**哦。ddd
84+
85+
看到这，请你先按上文提示把代码实现一下。
86+
87+
- 最后，发现还要对连续出现的重复的`num` 进行特别处理，即相同的`num` 对应的`answer` 中的值应该是一样的。处理方法有多种，怎么处理最简单呢？
88+
89+
ddd 用一个`Map`，`key`为`num`, 相同的`key` 直接使用`key` 对应的`值`。ddd
90+
91+
##复杂度
92+
93+
- 时间复杂度:`O(N * logN)`.
94+
- 空间复杂度:`O(N)`.
95+
96+
##Python
97+
98+
```python
99+
classSolution:
100+
deffindMaxSum(self,nums1: List[int],nums2: List[int],k:int) -> List[int]:
101+
num_index_list= [(num, index)for index, numinenumerate(nums1)]# key 1
102+
num_index_list.sort()
103+
104+
answer= [None]*len(nums1)
105+
k_max_nums= []
106+
sum_=0
107+
num_to_sum= defaultdict(int)# key 2
108+
109+
for i, num_indexinenumerate(num_index_list):
110+
num, index= num_index
111+
112+
if numin num_to_sum:
113+
answer[index]= num_to_sum[num]
114+
else:
115+
answer[index]= sum_
116+
num_to_sum[num]= sum_
117+
118+
heapq.heappush(k_max_nums, nums2[index])
119+
sum_+= nums2[index]
120+
121+
iflen(k_max_nums)> k:
122+
num= heapq.heappop(k_max_nums)# key 3
123+
sum_-= num
124+
125+
return answer
126+
```
127+
128+
##Other languages
129+
130+
```java
131+
// Welcome to create a PR to complete the code of this language, thanks!
132+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp