每日算法 - 2024年04月18日
1481. 不同整数的最少数目
题目
思路
贪心 + 哈希表
解题过程
题目要求我们移除
k个元素后，数组中剩余不同整数的最少数目。为了使得剩余的整数种类最少，我们应该优先移除那些出现次数最少的整数。这是一个典型的贪心策略。具体步骤如下：
- 使用哈希表（
HashMap）统计数组arr中每个整数出现的次数。- 获取哈希表中所有不同整数的出现次数。我们可以创建一个新数组
nums，将哈希表中记录的每个整数的出现次数（values）存入这个新数组。- 对存储出现次数的新数组
nums进行升序排序。这样，我们就得到了一个按元素出现次数从小到大排序的列表。- 遍历排序后的次数数组
nums。对于每个次数x：
- 如果当前的
k大于或等于x，说明我们可以将对应出现次数为x的这种整数全部移除。我们将k减去x，并将不同整数的种类数len减 1。- 如果当前的
k小于x，说明我们无法移除所有出现次数为x的这种整数（或者之前的移除操作已经用完了k），此时移除过程结束，直接跳出循环。- 最后返回剩余的不同整数种类数
len。
复杂度
- 时间复杂度: O(N log N)。其中 N 是数组
arr的长度。遍历数组统计频率需要 O(N)，将频率存入新数组最多需要 O(U)（U 是不同元素的数目，U <= N），排序频率数组需要 O(U log U)，最后遍历频率数组需要 O(U)。因此，瓶颈在于排序，总体时间复杂度为 O(N log N)。 - 空间复杂度: O(N)。哈希表最多存储 N 个元素（如果所有元素都不同），频率数组最多存储 N 个频率。
Code
class Solution {public int findLeastNumOfUniqueInts(int[] arr, int k) {Map<Integer, Integer> hash = new HashMap<>();for (int x : arr) {hash.put(x, hash.getOrDefault(x, 0) + 1);}int len = hash.size();int[] nums = new int[len];int i = 0;for (int key : hash.keySet()) {nums[i++] = hash.get(key);}Arrays.sort(nums);for (int x : nums) {if (k >= x) {k -= x;len--;} else {break;}}return len;}
}
1403. 非递增顺序的最小子序列
题目
思路
贪心
解题过程
题目的核心要求是找到一个子序列，其元素和严格大于未包含在子序列中的元素和。附加条件是，在满足核心要求的子序列中，选择长度最小的；如果长度依然相同，选择元素总和最大的。
为了同时满足这些条件，我们可以采用贪心策略：
- 对原数组
nums进行排序。- 计算整个数组的总和
totalSum。- 初始化子序列和
subsequenceSum = 0和子序列列表result。- 从数组的最大元素开始，依次将元素添加到子序列
result中，并累加到subsequenceSum。- 在每添加一个元素后，检查
subsequenceSum是否已经严格大于totalSum - subsequenceSum（即剩余元素的和）。- 一旦满足
subsequenceSum > totalSum - subsequenceSum，就停止添加元素。这种策略能保证：
- 满足核心条件：循环终止条件就是子序列和大于剩余元素和。
- 最小长度：因为我们是从大到小添加元素，每次添加都使得
subsequenceSum增长最快，所以能最快满足条件，从而保证子序列长度最小。- 最大和：在满足最小长度的条件下，由于我们选择的都是当前可选的最大元素，因此子序列的总和也是最大的。
- 非递增顺序：由于我们是按从大到小的顺序添加的，结果列表
result自然就是非递增顺序。
复杂度
- 时间复杂度: O(N log N)。主要是排序数组所需的时间。
- 空间复杂度: O(N) 或 O(log N)。排序可能需要 O(log N) 到 O(N) 的额外空间（取决于排序算法实现）。结果列表
result最多存储 N 个元素，因此空间复杂度为 O(N)。
Code
class Solution {public List<Integer> minSubsequence(int[] nums) {List<Integer> ret = new ArrayList<>();int totalSum = 0;for (int x : nums) {totalSum += x;}// 升序排序Arrays.sort(nums);int subsequenceSum = 0;// 从大到小遍历（排序后从后往前）for (int i = nums.length - 1; i >= 0; i--) {subsequenceSum += nums[i];ret.add(nums[i]);// 检查子序列和是否大于剩余元素和if (subsequenceSum > totalSum - subsequenceSum) {break;}}return ret;}
}
2389. 和有限的最长子序列（复习）
题目
这是第二次做这道题，思路在之前的博客中有详细记录。详情题解见 每日算法-250407。
简要思路：为了得到和不超过 queries[i] 的最长子序列，我们应该贪心地选择数值最小的元素。因此，先对 nums 排序，然后计算其前缀和。对于每个 query，在前缀和数组中进行二分查找，找到第一个大于 query 的位置 p，则满足条件的最长子序列长度即为 p。
Code
class Solution {public int[] answerQueries(int[] nums, int[] queries) {Arrays.sort(nums);for (int i = 1; i < nums.length; i++) {nums[i] += nums[i - 1];}for (int i = 0; i < queries.length; i++) {queries[i] = check(nums, queries[i]);}return queries;}private int check(int[] arr, int t) {int left = 0, right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] <= t) {left = mid + 1;} else {right = mid - 1;}}return left;}
}
)
