Алгоритм для нахождения высоких / низких чисел с максимум 1,5n сравнений

Question

Я немного подумал над этим домашним заданием. Учитывая числовой массив размера n, спроектируйте алгоритм, который найдет верхние и нижние значения с максимум 1,5n сравнениями.

Моя первая попытка была

int high=0
int low= Number.MaxValue //problem statement is unclear on what type of number to use
Number numList[0 . . n] //number array, assuming unsorted

for (i=0, i < n, i++) {
  if (numList[i] > high)
    high = numList[i]

  else if (numList[i] < low)
    low = numList[i]

}

Моя проблема в том, что каждая итерация цикла имеет одну из трех возможностей:

• найдено низкое значение - сделано 1 сравнение
• найдено высокое значение - сделано 2 сравнения
• ничего не найдено - сделано 2 сравнения

Таким образом, для обхода всего массива можно сделать максимум 2n сравнений, что очень далеко от проблемного максимального требования 1,5n сравнений.

Answer 1

Начните с пар чисел и найдите локальные минимальные и максимальные значения (n / 2 сравнения). Затем найдите глобальный максимум из n / 2 локальных максимумов (n / 2 сравнения) и аналогично глобальному минимуму из локальных mins (n ​​/ 2 сравнения). Всего сравнений: 3 * n / 2!

For i in 0 to n/2: #n/2 comparisons
    if x[2*i]>x[2*i+1]:
        swap(x,2*i,2*i+1)

global_min = min( x[0], x[2], ...) # n/2 comparisons
global_max = max( x[1], x[3], ...) # n/2 comparisons

Обратите внимание, что приведенное выше решение меняет массив. Альтернативный раствор:

Initialize min and max
For i = 0 to n/2:
    if x[2*i]<x[2*i+1]:
        if x[2*i]< min:
            min = x[2*i]
        if x[2*i+1]> max:
            max = x[2*i+1]
    else:
        if x[2*i+1]< min:
            min = x[2*i+1]
        if x[2*i]> max:
            max = x[2*i]

Answer 2

Я знаю, что на это уже был дан ответ, но в случае, если кто-то ищет другой способ подумать об этом.Этот ответ похож на * * * * Лестера , но может обрабатывать нечетные значения n без разрывов и все равно будет проводить максимум 1,5n сравнений.Секрет в модуле.;)

В качестве побочного эффекта от гарантии, что мы поместим последнее значение в соответствующий подмассив, второй элемент в данный список будет сравниваться и размещаться дважды.Однако, поскольку мы не меняем исходный массив и нас интересуют только максимум и минимум набора, это на самом деле не имеет значения.

Initialize lowArray and highArray
Initialize subArrayCounter to 0

For i = 0; i < n; i+=2
    X = givenList[i];
    Y = givenList[(i+1)%n];
    If(x < y)
        lowArray[subArrayCounter] = x;
        highArray[subArrayCounter] = y;
        subArrayCounter++;
    else
        lowArray[subArrayCounter] = y;
        highArray[subArrayCounter] = x;
        subArrayCounter++;

Initialize low to lowArray[0];
Initialize high to highArray[0];

For i = 1; i < lowArray.length; i++
    If(lowArray[i] < low)
        Low = lowArray[i];

For i = 1; i < highArray.length; i++
    If(highArray[i] > high)
        High = highArray[i]

Answer 3

Это тот же ответ, что и у ElKamina, но поскольку я уже начал писать псевдокод, я решил закончить и опубликовать его.

Идея заключается в сравнении пар значений(n / 2 сравнения), чтобы получить массив высоких значений и массив низких значений.С каждым из этих массивов мы снова сравниваем пары значений (2 * n / 2 сравнения), чтобы получить максимальное и минимальное значения соответственно.

n/2 + 2*n/2 = 1.5n comparisons

Вот псевдокод:

int[] highNumList;
int[] lowNumList;

for (i = 0, i < n, i+=2)
{
    a = numList[i];
    b = numList[i+1];
    if (a > b)
    {
        highNumList.Add(a);
        lowNumlist.Add(b);
    }
    else
    {
        highNumlist.Add(b);
        lowNumList.Add(a);
    }
}

int high = highNumList[0];
int low = lowNumList[0];

for (i = 0, i < n/2, i+=2)
{
    if (highNumList[i] < highNumList[i+1])
        high = highNumList[i+1]
    if (lowNumList[i] > lowNumList[i+1])
        low = lowNumList[i+1]
}

Этот код не учитывает, что n не является четным или исходный массив пуст.

Answer 4

Это вопрос, который у меня возник во время интервью, и я нашел ответ с небольшим намеком интервьюера, который был «Как вы сравниваете два числа?»(это действительно помогло).

Вот объяснение:

Допустим, у меня есть 100 чисел (вы можете легко заменить его на n, но оно лучше работает для примера, если n - четное число).Что я делаю, так это то, что я разбил его на 50 списков по 2 числа.Для каждой пары я делаю одно сравнение, и я готов (что к настоящему времени делает 50 сравнений), тогда мне просто нужно найти минимум минимумов (который составляет 49 сравнений) и максимум максимумов (который также составляет 49 сравнений)) такое, что нужно сделать 49 + 49 + 50 = 148 сравнений.Мы закончили!

Примечание: чтобы найти минимум, мы поступаем следующим образом (в псевдокоде):

    n=myList.size();
    min=myList[0];
    for (int i(1);i<n-1;i++)
    {
    if (min>myList[i]) min=myList[i];
    }
    return min;

И мы находим его в (n-1) сравнениях.Код почти одинаков для максимума.