4

我有一个整数数组，value[]. 它可以是任何长度。

我需要找到最小的数字。我正在处理面试街的一个问题。我的Time Exceeded出现错误。我需要提高计算最小值的速度，因为迭代变得更糟。

我对使用 Java 集合或其他任何东西很感兴趣，因此任何人都可以提出一些改进代码的建议。

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

5 回答 5

9

没有更好的算法来查找数组中的最小或最大元素。您必须查看每个元素。也许你会在其他地方浪费时间——例如阅读输入。

于 2012-05-01T16:07:41.587 回答
6

该算法似乎可以很好地找到数组的最小值。如果对数组中可能包含的元素一无所知，则需要检查每个元素，因此您的性能是线性的（与数组中元素的数量成正比）。

如果元素是完全有序的，您只需查找第一个（或最后一个，dependng 或 ordering）元素（恒定时间性能）

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

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

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

于 2012-05-01T16:08:10.613 回答
2

如果您使用数组作为元素的存储结构，那么您别无选择，只能遍历所有元素以找到最小元素。但是，您的算法在 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);
于 2012-05-01T16:26:28.467 回答
0

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

于 2012-05-01T16:21:12.553 回答
0

获得最小数字的简单方法.. 

 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]);
        }
    }
于 2013-05-15T13:08:45.597 回答