数组大小减半
题目描述
给你一个整数数组 arr。你可以从中选出一个整数集合,并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。...大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的,它的结果数组为 [3,3,3,3,5,5,5],新数组长度大于原数组的二分之一。...优化
上面的代码我们对统计计数进行了传统排序,复杂度就达到了 O(nlogn)。我们是否有方法降低这个复杂度呢?
这里介绍一种不那么传统的排序方式 -- 桶排序。...我们先来看一个栗子:
我们现在假设有 2000 个学生,他们刚进行完一次考试,每个人考试成绩的范围是 [1, 100]。现在我们需要把他们这一次考试的成绩按照升序进行排序。...所以在优化过程中,引入了一种不是特别常见的排序方式,并进行了说明。希望还没有接触过的小伙伴们能有所收获。