1338. Reduce Array Size to The Half

题目信息

题号:

1338

难度:

Medium

主题:

数组、频次统计、贪心

原题:

LeetCode 1338

重点:

选择一个数值集合并删除数组中所有属于该集合的元素;使剩余长度至多为原来一半并最小化集合大小

题目重述

给定偶数长度的整数数组 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
解释:每选择一个值只能删除一个元素,因此至少选择两个值。