在不改变其位置的情况下修改数组中最大的元素？-解网

问：

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

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

关于如何处理此类问题的任何建议？

Java 数组

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

@Jeff Paulsen：当然，如果我们能保证 M 会保持小，这是一个简单的解决方案，而且效果很好。对于小值来说，最小堆的额外开销（首先为它找到一个额外的库或自己实现它）肯定会更糟。但是对于可能的 M=N，它会变成 N^2（我认为你不能在这里比 n log m 做得更好，听起来比较排序边界定理也应该在这里适用）

0赞 Chris Morgan 5/14/2011

@Jeff我不知道有任何排序算法比任意数据的 O（n）更快。en.wikipedia.org/wiki/......

1赞 Lou Franco 5/14/2011 #3

遍历数组并跟踪两个最大项目的索引和值

一个。使用 -1 初始化跟踪器作为索引，MIN_INT初始化跟踪器作为数组的值或前两个值

b.在循环的每个步骤中，将当前值与两个跟踪器值进行比较，并在必要时进行更新
递增这两个项目

为此，您选择的任何算法都应该是 O（n）。排序和 n 次传递是矫枉过正的。

0赞 tarkeshwar 5/14/2011 #4

使用 here 和 here 的技术找到第 n 个最大的元素（称为 K）（可以在线性时间内完成），然后遍历修改所有元素的数组 >= K。

int[] indices = new int[2];
int[] maximas = new int[] { 0, 0 };
int[] data = new int[] { 3, 4, 5, 1, 9 };
for (int i = 0; i < 5; ++i)
{
    if (data[i] > maximas[1])
    {
            maximas[0] = maximas[1];
            maximas[1] = data[i];
            indices[0] = indices[1];
            indices[1] = i;
    } 
    else if (data[i] > maximas[0])
    {
            maximas[0] = data[i];
            indices[0] = i;
    }
}

没有测试它，但我认为它应该:)

0赞 Marino Šimić 5/14/2011 #6

我对此有点强硬，但我不能实现比最坏的情况更多：

O（ n + （m-n） * n ）：（m > n）

最佳案例：

O（米）：（m <= n）

其中 m = 值数，n = 要搜索的最大值数

这是 C# 中的实现，但你可以很容易地适应 java：

        int n = 3;
        List<int> values = new List<int> {1,1,1,8,7,6,5};
        List<int> greatestIndexes = new List<int>();

        for (int i = 0; i < values.Count; i++) {
            if (greatestIndexes.Count < n)
            {
                greatestIndexes.Add(i);
            }
            else {
                int minIndex = -1, minValue = int.MaxValue;
                for (int j = 0; j < n; j++)
                {
                    if (values[greatestIndexes[j]] < values[i]) {

                        if (minValue > values[greatestIndexes[j]])
                        {
                            minValue = values[greatestIndexes[j]];
                            minIndex = j;
                        }
                    }
                }
                if (minIndex != -1)
                {
                    greatestIndexes.RemoveAt(minIndex);
                    greatestIndexes.Add(i);
                }
            }
        }

        foreach (var i in greatestIndexes) {
            Console.WriteLine(values[i]);
        }

输出：

8
7
6

上一个：图像在 .jar 文件中不起作用

下一个：如何检查另一个字符串中是否存在一个确切的字符串？

在不改变其位置的情况下修改数组中最大的元素？

Modifying the greatest elements of an array without changing their position?

评论

评论

评论

评论