java - 修改数组的最大元素而不改变它们的位置？

Question

我试图弄清楚如何修改数组的n个最大元素而不修改它们的位置。例如，假设我有一个整数数组 {5, 2, 3, 4, 8, 9, 1, 3};我想将最大的两个元素加 1，使数组成为 {5, 2, 3, 4, 9, 10, 1, 3}。

当我尝试实现这些方法时，我能想到的所有方法最终都感觉笨拙且不直观，这向我表明我没有正确思考它。例如，我可以使用 TreeMap，将数组的值作为键，将它们的索引作为值来查找最大值，修改它们，然后将它们放回数组中，但随后我必须实现自己的比较器以相反的顺序对 TreeMap 进行排序(除非有我不知道的更简单的方法？)。我还考虑将数组的内容复制到列表中，迭代n次，每次找到最大元素及其索引，将修改后的最大元素放回到该索引处的数组中，删除列表中的元素，然后重复，但这对我来说感觉很草率且效率低下。

关于如何解决此类问题有什么建议吗？

Answer 1

最简单的事情是扫描数组，并存储 n 个最高值的索引。增加这些元素的值。

这将是 O(n) 性能，我认为没有任何更高级的方法可以击败它。

编辑添加:您最多可以在 O(n) 内对数组进行排序，在这种情况下您可以非常快速地获得 n 个最高值，但要求是不改变元素的位置，所以您'如果您想这样做，则必须从数组的副本开始(或保留排序信息，以便之后可以将所有内容放回原处)。