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

Если поиск минимума выполняется один раз, просто просмотрите список и найдите минимум.

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

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

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

Он должен выглядеть примерно так:

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

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

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

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

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

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.

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

std::min_element
std::max_element

can be used.

Вам также нужно пройти через массив, запоминая наименьшее значение, которое вы видели до сих пор. Примерно так:

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

Ответ Ричи близок. Это зависит от языка. Вот хорошее решение для 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. Если работа, выполняемая в цикле, незначительна, то сравнение циклов занимает значительную долю времени.

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