最大化数组的伟大值
难度:
标签:
题目描述
You are given a 0-indexed integer array nums. You are allowed to permute nums into a new array perm of your choosing.
We define the greatness of nums be the number of indices 0 <= i < nums.length for which perm[i] > nums[i].
Return the maximum possible greatness you can achieve after permuting nums.
Example 1:
Input: nums = [1,3,5,2,1,3,1] Output: 4 Explanation: One of the optimal rearrangements is perm = [2,5,1,3,3,1,1]. At indices = 0, 1, 3, and 4, perm[i] > nums[i]. Hence, we return 4.
Example 2:
Input: nums = [1,2,3,4] Output: 3 Explanation: We can prove the optimal perm is [2,3,4,1]. At indices = 0, 1, and 2, perm[i] > nums[i]. Hence, we return 3.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109
代码结果
运行时间: 47 ms, 内存: 35.5 MB
/*
* 题目思路：
* 1. 对 nums 进行排序得到 sortedNums。
* 2. 将 sortedNums 转换为一个迭代器。
* 3. 使用 Stream API 遍历 nums，对于每个元素 nums[i]，找到大于 nums[i] 的最小元素。
* 4. 如果找到，则计数，并从迭代器中移除该元素。
*/
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.stream.Collectors;
public class Solution {
public int maxGreatness(int[] nums) {
List<Integer> sortedNums = Arrays.stream(nums).boxed().sorted().collect(Collectors.toList());
Iterator<Integer> iterator = sortedNums.iterator();
int count = 0;
for (int num : nums) {
while (iterator.hasNext()) {
if (iterator.next() > num) {
count++;
break;
}
}
}
return count;
}
}解释
方法:
题解采用了一种贪心算法的思路，主要目标是尽可能让新数组perm中的元素大于原数组nums中对应位置的元素。首先对原数组进行排序，得到一个非降序的数组A。接着，使用一个指针i从0开始，遍历排序后的数组A。对于每个元素x，如果x大于A[i]（即x能够大于其在原数组中对应位置的元素），则i增加1，这样做可以确保已处理的元素个数即为满足条件的最大个数。最后，返回i的值，即为最大伟大值。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到的`原数组的对应位置`是怎样确定的，给定排序后的数组A和原数组nums的不同顺序，如何确保比较的正确性？
▷🦆
在题解的逻辑中，为什么选择对数组进行非降序排序，而不是非升序或其他排序方式？
▷🦆
算法中使用单指针遍历排序后的数组，为什么这种方法足以找到最大的伟大值？是否有可能存在未考虑的情况导致计数不准确？
▷