В массиве есть N значений, а одно из них - наименьшее значение. Как я могу найти наименьшее значение наиболее эффективно?
Наилучшее обнаружение наименьшего значения в массиве
Ответ 1
Если они несортированы, вы не можете много сделать, но посмотрите на каждый, что есть O (N), и когда вы закончите, вы узнаете минимум.
Псевдо-код:
small = <biggest value> // such as std::numerical_limits<int>::max
for each element in array:
if (element < small)
small = element
Лучший способ, на который мне ответил Ben, - это просто инициализировать маленький с первым элементом:
small = element[0]
for each element in array, starting from 1 (not 0):
if (element < small)
small = element
Вышеописанное завершено в заголовке algorithm как станд:: min_element.
Если вы можете сохранить свой массив отсортированным по мере добавления элементов, то поиск его будет O (1), так как вы можете сохранить наименьший фронт.
Это так хорошо, как получается с массивами.
Ответ 2
В stl содержится множество методов, которые должны использоваться в зависимости от проблемы.
std::find
std::find_if
std::count
std::find
std::binary_search
std::equal_range
std::lower_bound
std::upper_bound
Теперь он содержит на ваших данных, какой алгоритм использовать. Этот Artikel содержит идеальную таблицу для выбора правильного алгоритма.
В специальном случае, когда min max должен быть определен, и вы используете std::vector или??? * массив
std::min_element
std::max_element
.
Ответ 3
Вам нужен слишком цикл через массив, помня наименьшее значение, которое вы видели до сих пор. Вот так:
int smallest = INT_MAX;
for (int i = 0; i < array_length; i++) {
if (array[i] < smallest) {
smallest = array[i];
}
}
Ответ 4
Если вы хотите быть действительно эффективным, и у вас есть достаточно времени, чтобы потратить, используйте инструкцию SIMD.
Вы можете сравнить несколько пар в одной инструкции:
r0 := min(a0, b0)
r1 := min(a1, b1)
r2 := min(a2, b2)
r3 := min(a3, b3)
__m64 _mm_min_pu8(__m64 a , __m64 b );
Сегодня каждый компьютер поддерживает его. Другие уже написали min функцию для вас:
http://smartdata.usbid.com/datasheets/usbid/2001/2001-q1/i_minmax.pdf
или использовать уже готовый library.
Ответ 5
Если массив отсортирован в порядке возрастания или убывания, вы можете найти его со сложностью O (1). Для массива возрастающего порядка первый элемент является наименьшим элементом, вы можете получить его через arr [0] (индексирование на основе 0). Если массив отсортирован в порядке убывания, последний элемент является наименьшим элементом, вы можете получить его с помощью arr [sizeOfArray-1].
Если массив не отсортирован, вам нужно выполнить итерацию по массиву, чтобы получить наименьший элемент. В этом случае временная сложность 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];
}
}
Вы можете рассчитать его в разделе ввода (когда вам нужно найти наименьший элемент из заданного массива)
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];
}
}
Также вы можете получить наименьший элемент встроенной функцией
#inclue<algorithm>
int smallest_element = *min_element(arr,arr+n); //here n is the size of array
Вы можете получить наименьший элемент любого диапазона, используя эту функцию например,
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)
Я использовал звездочку (*) перед функцией min_element(). Потому что он возвращает указатель наименьшего элемента. Все коды находятся в С++. Вы можете найти максимальный элемент в обратном порядке.
Ответ 6
Решение O (1) может состоять в том, чтобы просто угадать: наименьшее число в вашем массиве будет часто 0. 0 размножается повсюду. Учитывая, что вы смотрите только на неподписанные числа. Но даже тогда: 0 достаточно. Кроме того, просмотр всех элементов для наименьшего числа - настоящая боль. Почему бы просто не использовать 0? Это может быть правильный результат!
Если собеседнику/вашему учителю не нравится этот ответ, попробуйте 1, 2 или 3. Они также попадают в большинство домашних заданий/интервью с числовыми массивами...
На более серьезной стороне:. Как часто вам понадобится выполнить эту операцию в массиве? Поскольку приведенные выше решения являются всеми O (n). Если вы хотите сделать это m раз в списке, вы будете постоянно добавлять новые элементы, почему бы не заплатить некоторое время и создать кучу? Тогда найти наименьший элемент действительно можно сделать в O (1), не приводя к обману.
Ответ 7
Если найти минимум - это одноразовая вещь, просто перейдите по списку и найдите минимум.
Если найти минимум - это очень обычная вещь, и вам нужно всего лишь работать с минимумом, используйте структуру данных кучи.
Куча будет быстрее, чем делать сортировку в списке, но компромисс вы можете найти только минимум.
Ответ 8
Если вы разрабатываете какую-то свою абстракцию собственного массива, вы можете получить O (1), если вы храните наименьшее добавленное значение в дополнительном атрибуте и сравниваете его каждый раз, когда новый элемент помещается в массив.
Он должен выглядеть примерно так:
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
Ответ Ричи близок. Это зависит от языка. Вот хорошее решение для 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" с "array_length" в сравнении циклов требует выборки и сравнения (две операции), тогда как сравнение "i" с "0" представляет собой один байт-код JVM операция. Если работа, выполняемая в цикле, ничтожно мала, то сравнение циклов потребляет значительную часть времени.
Конечно, другие отметили, что инкапсуляция массива и управление вставками помогут. Если получение минимума было ВСЕ, то вам нужно, чтобы список в отсортированном порядке не нужен. Просто сохраните переменную экземпляра, которая содержит самое маленькое вложенное до сих пор, и сравните ее с каждым значением, поскольку оно добавлено в массив. (Конечно, это не удастся, если вы удалите элементы. В этом случае, если вы удалите текущее самое низкое значение, вам нужно выполнить сканирование всего массива, чтобы найти новое минимальное значение.)
Ответ 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
Процедура:
Мы можем использовать функцию min_element (массив, массив + размер). Но это итератор
которые возвращают адрес минимального элемента. Если мы будем использовать * min_element (массив, массив + размер), то он вернет минимальное значение массива.
Реализация С++
#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];
}