Java中最小的数组元素

Question

我有一个整数数组value[]，它的长度可以是任意值。

我需要找到最小的数字。我正在做一道面试题，但是我的程序超时了。我需要提高计算最小值的速度，因为遍历数组会变得更糟。

我想使用Java集合或其他方法，希望能够得到一些改进代码的建议。

int mini=value[0];
for (int i = 1; i < noinps; i++) {
    if(mini>value[i]) {
        mini=value[i];
    }
}
System.out.println(mini);

- special

---

你现在还在面试吗？如果是，发布这个问题不会被视为作弊吗？ - duffymo

@duffymo 我猜那只是语言障碍问题（现在时和现在进行时之间的区别）。至少我希望是这样！ - Andrzej Doyle

我认为他在谈论https://www.interviewstreet.com。 - dogbane

我只是在寻求建议，而不是完整的答案。我想知道我的逻辑是否正常工作。 - special

Answer 1

在查找数组中的最小或最大元素方面，不存在更好的算法。您必须查看每个元素。也许您会在其他地方浪费时间 - 例如读取输入。

- Petar Minchev

---

+1，同意。除非您先前预缓存了某些信息（例如，在填充数组时跟踪最小值），否则没有比依次检查每个元素更快的方法。 - Andrzej Doyle

线性搜索是未排序数组的最佳算法，我认为它是这样的（否则，问题就是平凡的）。 - Yuka

Answer 2

该算法在查找数组的最小值方面表现良好。如果对于可能包含在数组中的元素一无所知，则需要检查每个元素，因此性能是线性的（与数组中元素数量成正比）。

如果元素完全有序，您可以直接查找第一个（或最后一个，具体取决于排序方式）元素（常数时间性能）。

如果元素是半有序的（例如，堆结构），则可以通过类似二分搜索的技术找到它（log(n)性能）。

如果元素是无序的，但您知道它们不能小于某个值，则可以在找到最小可能值时停止搜索。

因此回到超时问题：如果元素是无序的，并且没有其他限制，那么您的算法就很好，因此超时必须来自程序的其他部分（例如，您正在尝试从控制台读取数据，但数据存储在文件中）。

- Attila

Answer 3

如果你使用数组作为元素的存储结构，那么你就只能循环遍历所有元素来查找最小元素。但是，由于你只需通过数组循环一次，因此你的算法复杂度为O(n)，效果良好。

如果数组大小非常巨大，则迭代会变得更糟糕。在这种情况下，我建议不要使用数组作为存储区域，如果你没有其他选择，那么在将元素放入数组之前，请尝试检查每个元素本身，这样你就不需要迭代数组来查找最小元素。

使用集合将是最佳方法。

ArrayList arrayList = new ArrayList();
//Add elements to Arraylist
arrayList.add(new Integer("23"));
arrayList.add(new Integer("1"));
arrayList.add(new Integer("134"));
arrayList.add(new Integer("22"));
arrayList.add(new Integer("0"));

/*
   To find maximum element of Java ArrayList use,
  static Object max(Collection c) method of Collections class.

   This method returns the maximum element of Java ArrayList according to
   its natural ordering.
*/

Object obj = Collections.max(arrayList);

System.out.println("Maximum Element of Java ArrayList is : " + obj);

- ylnsagar

Answer 4

使用2个线程，每个线程取数组的一半，找到其一半中的最小值，然后将结果写入变量。之后，在主线程中比较这两个结果。

- Eng.Fouad

Answer 5

获取最小数的简单方法..

 import java.util.Arrays;
    public class demoClass {
        public static void main(String[] args) {

                  // consider the below array of data
                    int[] numbers = {12,22,32,43,53};

                   // first sort the array using sort keyword
                   Arrays.sort(numbers);

                 System.out.println("Smallest Number = "+numbers[0]);
        }
    }

- Gowtham Gows