C++ 最有效地查找数组中的最小值
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1042507/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding smallest value in an array most efficiently
提问by Muhammad Akhtar
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个值，其中一个是最小值。如何最有效地找到最小值？
回答by GManNickG
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 Bento 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 algorithmheader 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.
这和数组一样好。
回答by Totonga
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 Artikelcontains 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
在应该确定 min max 并且您使用 std::vector 或 ???* 数组的特殊情况下
std::min_element
std::max_element
can be used.
可以使用。
回答by Tomas Kubes
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.
或使用已经准备好的库。
回答by RichieHindle
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];
}
}
回答by Taohidul Islam
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[sizeOfArray-1]得到它。
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)
您可以在输入部分计算它（当您必须从给定数组中找到最小元素时）
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() 函数之前使用了星号 (*)。因为它返回最小元素的指针。所有代码都在 C++ 中。您可以以相反的方式找到最大元素。
回答by rashedcs
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(array, array+size)函数。但是它
返回最小元素地址的迭代器。如果我们使用*min_element(array, array+size)那么它将返回数组的最小值。
C++ implementation
C++ 实现
#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;
}
回答by Daren Thomas
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) 中完成，而不会导致作弊。
回答by clemahieu
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.
如果找到最小值是一件很常见的事情，而您只需要对最小值进行操作，那么使用 Heap 数据结构。
A heap will be faster than doing a sort on the list but the tradeoff is you can only find the minimum.
堆比对列表进行排序要快，但权衡是您只能找到最小值。
回答by Michael
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;
}
回答by Paul Chernoch
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.)
当然，其他人指出封装数组和控制插入会有所帮助。如果您只需要获得最小值，则无需按排序顺序排列列表。只需保留一个实例变量，其中包含迄今为止插入的最小变量，并将其与添加到数组中的每个值进行比较。（当然，如果您删除元素，这将失败。在这种情况下，如果您删除当前的最低值，则需要扫描整个数组以找到新的最低值。）
