Нахождение наименьшего значения в массиве наиболее эффективно

В массиве есть N значений, и одно из них является наименьшим значением. Как я могу найти наименьшее значение наиболее эффективно?

 RichieHindle25 июн. 2009 г., 09:52
@ Майк: Предположительно, Мухаммед в настоящее время не в интервью. 8-)
 Naveen25 июн. 2009 г., 09:17
если это случайный массив, вы можете намного лучше, чем O (n)
 J-16 SDiZ25 июн. 2009 г., 09:10
признаки это вопрос HW
 StriplingWarrior26 июн. 2009 г., 21:32
Если вы легко можете найти ответ с помощью поиска в Google, должен ли он действительно быть в StackOverflow?
 slypete26 июн. 2009 г., 22:02
Они отсортированы?

Ответы на вопрос(13)

вы можете найти его со сложностью 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 (). Потому что он возвращает указатель наименьшего элемента. Все коды на с ++. Вы можете найти максимальный элемент в противоположном направлении.

//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];
    }
}
Решение Вопроса

вы не можете ничего делать, но смотрите на каждый из них, то есть O (N), и когда вы закончите, вы узнаете минимум.

Псевдо-код:

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

Лучший способ напомнилБен для меня было просто инициализировать маленький с первым элементом:

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

Выше, завернутый валгоритм заголовок какстанд :: min_element.

Если вы можете сохранить ваш массив отсортированным при добавлении элементов, то для него будет установлено значение O (1), так как вы можете оставить наименьшее число спереди.

Это так же хорошо, как это происходит с массивами.

 25 июн. 2009 г., 11:15
Вы должны вернуть null для пустого контейнера.
 25 июн. 2009 г., 09:30
что может быть хорошо, если вам нужно быстро узнать наименьшее значение, и вы не добавляете новые элементы постоянно.
 25 июн. 2009 г., 11:08
Обратите внимание, что & quot; small = element [0] & quot; небезопасно, если массив может быть пустым.
 25 июн. 2009 г., 09:08
Хорошо, элемент поиска будет O (1), но сохранение отсортированного массива будет стоить дороже (зависит от вашего алгоритма сортировки)
 25 июн. 2009 г., 11:12
Правда. Каково стандартное соглашение о нахождении минимума (maxmimum и т. Д.) Пустого контейнера? Я не думаю, что вы действительно можете вернуть что-нибудь полезное, кроме максимального значения, которое может не существовать для пользовательских типов.

наименьшее число в вашем массиве часто будет 0. 0 появляется везде. Учитывая, что вы смотрите только на беззнаковые номера. Но даже тогда: 0 достаточно хорошо. Кроме того, просмотр всех элементов для наименьшего числа является настоящей болью. Почему бы просто не использовать 0? Это может быть правильный результат!

Если интервьюеру / вашему учителю не нравится этот ответ, попробуйте 1, 2 или 3. В конечном итоге они также попадают в большинство числовых массивов сценария домашней работы / интервью ...

On a more serious side: Как часто вам нужно будет выполнять эту операцию над массивом? Потому что все вышеуказанные решения - это O (n). Если вы хотите сделать это m раз в списке, вы будете все время добавлять новые элементы, почему бы не уделить время заранее и создать кучу? Тогда действительно можно найти самый маленький элемент в O (1), не приводя к обману.

 25 июн. 2009 г., 22:15
Да, набор отсортирован. Тем не менее, есть куча функций, которые вы можете использовать.
 25 июн. 2009 г., 17:27
Я уверен, что в stl была функция heapify (или аналогичная) ... Разумно ли рассчитывать на порядок сортировки std :: set?
 25 июн. 2009 г., 18:08
Вы не должны на это рассчитывать. Просто предоставь свой :-)
 25 июн. 2009 г., 13:14
Вам не нужно создавать кучу самостоятельно. Используйте std :: set, который определяет порядок сортировки.
 13 апр. 2010 г., 17:27
Нет даже необходимости использовать дорогой набор. Просто используйте упаковщик массива с автоматически обновляемымmin переменная на вставке.

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];
    }
}

Я перебираю массив в обратном порядке, потому что сравнивая & quot; i & quot; на "массив_длину" в цикле сравнения требуется выборка и сравнение (две операции), тогда как сравнение «i» до "0" является одной операцией байт-кода JVM. Если работа, выполняемая в цикле, незначительна, то сравнение цикла занимает значительную долю времени.

Конечно, другие отметили, что инкапсуляция массива и управление вставками помогут. Если для получения минимума было ВСЕ, что вам нужно, хранить список в отсортированном порядке не нужно. Просто сохраните переменную экземпляра, которая содержит наименьшую вставленную часть, и сравните ее с каждым значением, когда оно добавляется в массив. (Конечно, это не удастся, если вы удалите элементы. В этом случае, если вы удалите текущее минимальное значение, вам нужно выполнить сканирование всего массива, чтобы найти новое минимальное значение.)

 12 июл. 2009 г., 22:20
& quot; Это зависит от языка. Вот хорошее решение для Java & quot; Зачем даже публиковать это вместе с информацией о JVM в вопросе C ++?

времени, чтобы использовать, используйте инструкцию 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

или использовать уже готовбиблиотека.

вы можете получить 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;
}
                //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);

помня наименьшее значение, которое вы когда-либо видели. Как это:

int smallest = INT_MAX;
for (int i = 0; i < array_length; i++) {
    if (array[i] < smallest) {
        smallest = array[i];
    }
}
 25 июн. 2009 г., 09:45
Я бы инициализировал наименьшее с первым элементом массива, затем итерировал бы от 1 до array_length. Кстати, вы забыли я в Int я = 0;
 25 июн. 2009 г., 09:57
@Ben: Просто не забудьте разобраться со случаем, когда массив пуст. 8-)
int small=a[0];
for (int x: a.length)
{
    if(a[x]<small)
        small=a[x];
}
 10 нояб. 2015 г., 17:59
Есть много других эквивалентных ответов на этот вопрос. Ваш ответ мало что дает.
 10 нояб. 2015 г., 16:41
Ваш ответ будет более значимым, если вы добавите несколько комментариев, объясняющих, почему это эффективный способ найти наименьшее значение.

просто переберите список и найдите минимум.

Если поиск минимума - это очень распространенная вещь, и вам нужно работать только с минимумом, используйте структуру данных Heap.

Куча будет быстрее, чем выполнять сортировку в списке, но компромисс в том, что вы можете найти только минимум.

которые следует использовать в зависимости от проблемы.

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

Теперь он содержит в ваших данных, какой алгоритм использовать. этоКод содержит идеальную таблицу, чтобы помочь выбрать правильный алгоритм.

В особом случае, когда должно быть определено min max и вы используете std :: vector или ??? * array

std::min_element
std::max_element

может быть использован.

 25 июн. 2009 г., 09:57
Зачем вызывать все эти алгоритмы, а не std :: min_element, который запрашивается в вопросе?
 25 июн. 2009 г., 13:11
Просто потому, что я не знаю этого. Но всегда O (N), если вы знаете больше о данных или ваши данные не хранятся в несортированном векторе, вы получаете большую производительность, используя другие алгоритмы. Я думаю, что упомянутый articel показывает, что вопрос о лучшем алгоритме всегда зависит от данных и контейнера.
Procedure:

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;
  }
 31 окт. 2016 г., 18:04
Я думаю, это лучший процесс, чтобы найти наименьшее число.

Ваш ответ на вопрос