1338. Reduce Array Size to The Half¶
题目信息¶
- 题号:
1338
- 难度:
Medium
- 主题:
数组、频次统计、贪心
- 原题:
- 重点:
选择一个数值集合并删除数组中所有属于该集合的元素;使剩余长度至多为原来一半并最小化集合大小
题目重述¶
给定偶数长度的整数数组 arr。选择若干不同数值组成集合,并从数组中删除所有值属于该集合的元素。
请返回使数组剩余元素数量不超过原长度一半所需的最小集合大小。
2 <= arr.length <= 10^5,数组长度为偶数,1 <= arr[i] <= 10^5。
自建示例¶
删除最高频值即可达到一半:
输入:arr = [1,1,1,2,2,3]
输出:1
解释:删除所有值为 1 的元素后剩余三个元素,恰为原长度一半。
所有值互不相同时需要选择一半的值:
输入:arr = [1,2,3,4]
输出:2
解释:每选择一个值只能删除一个元素,因此至少选择两个值。