在数组中最有效地找到最小值。

There are N values in the array, and one of them is the smallest value. How can I find the smallest value most efficiently?

数组中有N个值，其中一个是最小值。如何最有效地找到最小值?

13 个解决方案

#1

If they are unsorted, you can't do much but look at each one, which is O(N), and when you're done you'll know the minimum.

如果它们是无序的，你不能做太多但是看看每一个，也就是O(N)当你完成时你会知道最小值。

---

Pseudo-code:

伪代码:

small = <biggest value> // such as std::numerical_limits<int>::max
for each element in array:
    if (element < small)
        small = element

A better way reminded by Ben to me was to just initialize small with the first element:

Ben提醒我的一个更好的方法是用第一个元素初始化small:

small = element[0]
for each element in array, starting from 1 (not 0):
    if (element < small)
        small = element

The above is wrapped in the algorithm header as std::min_element.

上面的内容以std::min_element的形式封装在算法头部。

---

If you can keep your array sorted as items are added, then finding it will be O(1), since you can keep the smallest at front.

如果您可以将数组排序为项，那么就会发现它是O(1)，因为您可以在前面保持最小值。

That's as good as it gets with arrays.

这和数组一样好。

#2

The stl contains a bunch of methods that should be used dependent to the problem.

stl包含了一堆方法，应该根据问题使用它们。

std::find
std::find_if
std::count
std::find
std::binary_search
std::equal_range
std::lower_bound
std::upper_bound

Now it contains on your data what algorithm to use. This Artikel contains a perfect table to help choosing the right algorithm.

现在它包含在你的数据上使用什么算法。这个Artikel包含一个完美的表，以帮助选择正确的算法。

---

In the special case where min max should be determined and you are using std::vector or ???* array

在需要确定最小最大值的特殊情况下，您使用的是std:::vector还是??*数组

std::min_element
std::max_element

can be used.

可以使用。

#3

You need too loop through the array, remembering the smallest value you've seen so far. Like this:

您需要在数组中循环，记住到目前为止看到的最小值。是这样的:

int smallest = INT_MAX;
for (int i = 0; i < array_length; i++) {
    if (array[i] < smallest) {
        smallest = array[i];
    }
}

#4

If you want to be really efficient and you have enough time to spent, use SIMD instruction.

如果你想要非常高效，并且你有足够的时间，使用SIMD指令。

You can compare several pairs in one instruction:

你可以在一个指令中比较几对:

r0 := min(a0, b0)
r1 := min(a1, b1)
r2 := min(a2, b2)
r3 := min(a3, b3)
__m64 _mm_min_pu8(__m64 a , __m64 b );

Today every computer supports it. Other already have written min function for you:

现在每台电脑都支持它。其他已经为您编写了min函数:

http://smartdata.usbid.com/datasheets/usbid/2001/2001-q1/i_minmax.pdf

http://smartdata.usbid.com/datasheets/usbid/2001/2001-q1/i_minmax.pdf

or use already ready library.

或者使用现成的库。

#5

If the array is sorted in ascending or descending order then you can find it with complexity O(1). For an array of ascending order the first element is the smallest element, you can get it by arr[0] (0 based indexing). If the array is sorted in descending order then the last element is the smallest element,you can get it by arr[sizeOfArray-1].

如果数组按升序或降序排序，那么您可以用复杂度为O(1)找到它。对于一个升序排列的数组，第一个元素是最小的元素，您可以通过arr[0](基于0的索引)获得它。如果数组按降序排序，那么最后一个元素就是最小的元素，您可以通过arr[sizeofarray1]获得它。

If the array is not sorted then you have to iterate over the array to get the smallest element.In this case time complexity is O(n), here n is the size of array.

如果数组没有排序，那么必须对数组进行迭代以获得最小的元素。在这种情况下，时间复杂度是O(n)，这里n是数组的大小。

int arr[] = {5,7,9,0,-3,2,3,4,56,-7};
int smallest_element=arr[0] //let, first element is the smallest one

for(int i =1;i<sizeOfArray;i++)  
{
    if(arr[i]<smallest_element)
    {
     smallest_element=arr[i];
    }
}

You can calculate it in input section (when you have to find smallest element from a given array)

您可以在input部分中计算它(当您必须从给定的数组中找到最小的元素时)

int smallest_element;
int arr[100],n;
cin>>n;
for(int i = 0;i<n;i++)
{
cin>>arr[i];
if(i==0)
{
    smallest_element=arr[i]; //smallest_element=arr[0];
}
else if(arr[i]<smallest_element)
{
smallest_element = arr[i];
}
}

Also you can get smallest element by built in function

你也可以通过内建函数得到最小的元素

#inclue<algorithm>
int smallest_element = *min_element(arr,arr+n); //here n is the size of array

You can get smallest element of any range by using this function such as,

你可以通过这个函数得到任何范围内最小的元素，比如，

int arr[] = {3,2,1,-1,-2,-3};
cout<<*min_element(arr,arr+3); //this will print 1,smallest element of first three element
cout<<*min_element(arr+2,arr+5); // -2, smallest element between third and fifth element (inclusive) 

I have used asterisk (*), before min_element() function. Because it returns pointer of smallest element. All codes are in c++. You can find the maximum element in opposite way.

我在min_element()函数之前使用了asterisk(*)。因为它返回最小元素的指针。所有代码都在c++中。你可以用相反的方法找到最大值。

#6

An O(1) sollution might be to just guess: The smallest number in your array will often be 0. 0 crops up everywhere. Given that you are only looking at unsigned numbers. But even then: 0 is good enough. Also, looking through all elements for the smallest number is a real pain. Why not just use 0? It could actually be the correct result!

一个O(1)排序可能只是猜测:数组中最小的数字通常是0。0突然出现在任何地方。假设你只看无符号的数字。但即便如此，0也足够好了。另外，从所有的元素中寻找最小的数字是一件非常痛苦的事情。为什么不用0呢?这可能是正确的结果!

If the interviewer/your teacher doesn't like that answer, try 1, 2 or 3. They also end up being in most homework/interview-scenario numeric arrays...

如果面试官/你的老师不喜欢这个答案，试试1、2或3。它们也最终出现在大多数家庭作业/面试场景的数字数组中……

On a more serious side: How often will you need to perform this operation on the array? Because the sollutions above are all O(n). If you want to do that m times to a list you will be adding new elements to all the time, why not pay some time up front and create a heap? Then finding the smallest element can really be done in O(1), without resulting to cheating.

更严重的问题是:需要多久对数组执行此操作?因为上面的集合都是O(n)如果你想要对一个列表做m次这样的操作，你会一直在添加新元素，为什么不先花点时间创建一个堆呢?然后找到最小的元素可以在O(1)中完成，而不会导致作弊。

#7

If finding the minimum is a one time thing, just iterate through the list and find the minimum.

如果找到最小值是一次性的事情，只需遍历列表并找到最小值。

If finding the minimum is a very common thing and you only need to operate on the minimum, use a Heap data structure.

如果找到最小值是非常常见的事情，并且只需要对最小值进行操作，那么使用堆数据结构。

A heap will be faster than doing a sort on the list but the tradeoff is you can only find the minimum.

堆将比在列表中进行排序要快，但是您只能找到最小值。

#8

If you're developing some kind of your own array abstraction, you can get O(1) if you store smallest added value in additional attribute and compare it every time a new item is put into array.

如果您正在开发某种自己的数组抽象，那么如果您将最小的附加值存储在附加属性中，并在每次将新项放入数组时对其进行比较，就可以得到O(1)。

It should look something like this:

它应该是这样的:

class MyArray
{
public:
    MyArray() : m_minValue(INT_MAX) {}

    void add(int newValue)
    {
        if (newValue < m_minValue) m_minValue = newValue;
        list.push_back( newValue );
    }

    int min()
    {
        return m_minValue;
    }

private:
    int m_minValue;
    std::list m_list;
}

#9

Richie's answer is close. It depends upon the language. Here is a good solution for java:

里奇的回答是关闭。这取决于语言。这里有一个很好的java解决方案:

int smallest =  Integer.MAX_VALUE;
int array[]; // Assume it is filled.
int array_length = array.length;
for (int i = array_length - 1; i >= 0; i--) {
    if (array[i] < smallest) {
        smallest = array[i];
    }
}

I go through the array in reverse order, because comparing "i" to "array_length" in the loop comparison requires a fetch and a comparison (two operations), whereas comparing "i" to "0" is a single JVM bytecode operation. If the work being done in the loop is negligible, then the loop comparison consumes a sizable fraction of the time.

我以相反的顺序遍历数组，因为在循环比较中将“I”与“array_length”进行比较需要获取和比较(两个操作)，而将“I”与“0”进行比较是一个JVM字节码操作。如果循环中所做的工作可以忽略不计，那么循环比较将花费相当大的一部分时间。

Of course, others pointed out that encapsulating the array and controlling inserts will help. If getting the minimum was ALL you needed, keeping the list in sorted order is not necessary. Just keep an instance variable that holds the smallest inserted so far, and compare it to each value as it is added to the array. (Of course, this fails if you remove elements. In that case, if you remove the current lowest value, you need to do a scan of the entire array to find the new lowest value.)

当然，其他人指出封装数组和控制插入将有所帮助。如果您只需要获得最小值，那么就不需要将列表按顺序排列。只需保存一个实例变量，该变量保存到目前为止插入的最小值，并将其与添加到数组中的每个值进行比较。(当然，如果删除元素，就会失败。在这种情况下，如果删除当前的最低值，则需要扫描整个数组以找到新的最低值。

#10

//find the min in an array list of #s
$array = array(45,545,134,6735,545,23,434);

$smallest = $array[0];
for($i=1; $i<count($array); $i++){
    if($array[$i] < $smallest){
        echo $array[$i];
    }
}

#11

                //smalest number in the array//
    double small = x[0];
    for(t=0;t<x[t];t++)
    {
         if(x[t]<small)
             {
                small=x[t];
            }
    }
    printf("\nThe smallest number is  %0.2lf  \n",small);

#12

---

Procedure:

We can use min_element(array, array+size) function . But it iterator
that return the address of minimum element . If we use *min_element(array, array+size) then it will return the minimum value of array.

我们可以使用min_element(数组、数组+大小)函数。但是它的迭代器返回最小元素的地址。如果我们使用*min_element(数组、数组+大小)，那么它将返回数组的最小值。

---

C++ implementation

  #include<bits/stdc++.h>
  using namespace std;

  int main()
  {
     int num;
     cin>>num;
     int arr[10];

     for(int i=0; i<num; i++)
     {
       cin>>arr[i];
     }


    cout<<*min_element(arr,arr+num)<<endl;

    return 0;
  }

#13

int small=a[0];
for (int x: a.length)
{
    if(a[x]<small)
        small=a[x];
}