0

我正在尝试解决一个问题，在该问题中，我需要编写 java 代码以在给定以下条件的情况下找到数组中的两个最大和最小数字：

- 每个元素都是一个实数

- 每个元素都是随机的

关于最佳方法的任何想法？

4

4 回答 4

6

您必须检查每个数字，因此您的最佳算法在数组长度上是线性的。

标准方法是只扫描数组，跟踪您目前看到的两个最小和最大的数字。

因此，鉴于 , firstMin, secondMin,firstMax分别secondMax是您目前看到的最小、第二小、最大和第二大的值，在循环的下一次迭代中：

if (value > firstMax) {
    secondMax = firstMax;
    firstMax = value;
} 
else if (value > secondMax) {
    secondMax = value;
}

if (value < firstMin) {
    secondMin = firstMin; 
    firstMin = value;
}
else if (value < secondMin) {
    secondMin = value;
}

在这个块的末尾，我们保持不变量 , firstMin, secondMin,firstMax分别secondMax是你迄今为止看到的最小、第二小、最大和第二大的值。这证明了正确性。

该算法在数组长度上是线性的，并且只检查每个值一次并进行最少的比较次数。它也在O(1)空间中，并且是最佳的，因为它只为顶部和底部两个值使用四个额外的内存位置。

于 2013-07-18T00:37:33.193 回答
5

有一个变量来跟踪您目前看到的 min、second_min、max 和 second_max 值。

您可以一一浏览数组的元素，并相应地更新您的最小/最大变量。以下是一些需要考虑的情况：

  • 如果当前元素小于您的最小值，请将您的最小值保存到 second_min 并更新您的最小值。
  • 如果当前元素大于您的最大值，请将您的最大值保存到 second_max 并更新您的最大值
  • 如果当前元素小于 second_min，但大于 min，则仅更新 second_min
  • 如果当前元素大于 second_max，但小于 max，则仅更新 second_max
于 2013-07-18T00:38:05.993 回答
2

是否需要超优化性能？如果不，

Arrays.sort( array );

查看第一个和最后两个元素。

于 2013-07-18T00:58:28.820 回答
0

我认为最好的方法是尽可能将数组用作堆或特殊数据结构。保持结构平衡和分类对您来说是最有效的。这意味着在数组中的某些索引处保留一些元素为空，因为数组的索引将是有关 ADT 的信息。http://en.wikipedia.org/wiki/Heap_(data_structure)

于 2013-07-18T00:54:08.540 回答