数组删除问题：最大删除数量

题目描述

给你一个长度为n的数组a，你现在有无数次选择每次选择 i,j 1<=i<j<=n 并且 a[i]等于a[j] 然后将a[i],a[i+1],a[i+2]...[j]删除求能够删除的数最多的是多少

样例

输入 5 1 2 3 3 2 输出 3

算法1

(哈希表) $O(n^2)$

首先将数组中的数存入哈希表中，然后枚举数组中的每一个数，对于每一个数，从哈希表中查找是否有相同的数，如果有，就删除这部分区间中的所有数，同时更新哈希表中的记录。最后统计删除的数的数量即可。

时间复杂度

枚举数组中的每一个数，对于每个数需要在哈希表中查找，所以时间复杂度为 $O(n^2)$。

参考文献

C++ 代码

算法2

(排序) $O(nlogn)$

首先将数组中的数排序，然后从前往后遍历，对于每一个数，统计它出现的次数，当它出现的次数大于等于2时，就将它的出现次数减1，这样就相当于删除了一部分区间中的数，同时更新数组中的记录。最后统计删除的数的数量即可。

时间复杂度

对数组进行排序的时间复杂度为 $O(nlogn)$，遍历数组的时间复杂度为 $O(n)$，所以总的时间复杂度为 $O(nlogn)$。

参考文献

C++ 代码