Найти второй по величине элемент в массиве с минимальным количеством сравнений

Question

Какое количество требуемых сравнений для массива размера N?

Answer 1

попробуйте это.

max1 = a[0].
max2.
for i = 0, until length:
  if a[i] > max:
     max2 = max1.
     max1 = a[i].
     #end IF
  #end FOR
return min2.

это должно работать как шарм.низкая сложность.

вот код Java.

int secondlLargestValue(int[] secondMax){
int max1 = secondMax[0]; // assign the first element of the array, no matter what, sorted or not.
int max2 = 0; // anything really work, but zero is just fundamental.
   for(int n = 0; n < secondMax.length; n++){ // start at zero, end when larger than length, grow by 1. 
        if(secondMax[n] > max1){ // nth element of the array is larger than max1, if so.
           max2 = max1; // largest in now second largest,
           max1 = secondMax[n]; // and this nth element is now max.
        }//end IF
    }//end FOR
    return max2;
}//end secondLargestValue()

Answer 2

Используйте сортировку подсчета, а затем найдите второй по величине элемент, начиная с индекса 0 до конца.Должно быть хотя бы 1 сравнение, максимум n-1 (когда есть только один элемент!).

Answer 3

Полагаю, следуйте приведенному выше «оптимальному алгоритму, использующему n + log n-2 сравнений», код, который я придумал и не использует двоичное дерево для хранения значения, будет следующим:

Во время каждого рекурсивного вызова размер массива уменьшается вдвое.

Таким образом, число сравнений равно:

1-я итерация: n / 2 сравнения

2-я итерация:n / 4 сравнения

3-я итерация: n / 8 сравнений

... До записи n итераций?

Следовательно, всего => n - 1 сравнений?

function findSecondLargestInArray(array) {
    let winner = [];
    if (array.length === 2) {
        if (array[0] < array[1]) {
            return array[0];
        } else {
            return array[1];
        }
    }
    for (let i = 1; i <= Math.floor(array.length / 2); i++) {
        if (array[2 * i - 1] > array[2 * i - 2]) {
            winner.push(array[2 * i - 1]);
        } else {
            winner.push(array[2 * i - 2]);
        }
    }
    return findSecondLargestInArray(winner);
}

Предполагая, что массив содержит 2 ^ n чисел.

Если существует 6 чисел, то 3 числа перейдут на следующий уровень, что не так.

Нужно как 8 цифр => 4 числа => 2 числа => 1 число => 2 ^ n число числа

Answer 4

Принятое решение от sdcvvc на C ++ 11.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <climits>

using std::vector;
using std::cout;
using std::endl;
using std::random_shuffle;
using std::min;
using std::max;

vector<int> create_tournament(const vector<int>& input) {
  // make sure we have at least two elements, so the problem is interesting
  if (input.size() <= 1) {
    return input;
  }

  vector<int> result(2 * input.size() - 1, -1);

  int i = 0;
  for (const auto& el : input) {
    result[input.size() - 1 + i] = el;
    ++i;
  }

  for (uint j = input.size() / 2; j > 0; j >>= 1) {
    for (uint k = 0; k < 2 * j; k += 2) {
      result[j - 1 + k / 2] = min(result[2 * j - 1 + k], result[2 * j + k]);
    }
  }

  return result;
}

int second_smaller(const vector<int>& tournament) {
  const auto& minimum = tournament[0];
  int second = INT_MAX;

  for (uint j = 0; j < tournament.size() / 2; ) {
    if (tournament[2 * j + 1] == minimum) {
      second = min(second, tournament[2 * j + 2]);
      j = 2 * j + 1;
    }
    else {
      second = min(second, tournament[2 * j + 1]);
      j = 2 * j + 2;
    }
  }

  return second;
}

void print_vector(const vector<int>& v) {
  for (const auto& el : v) {
    cout << el << " ";
  }
  cout << endl;
}

int main() {

  vector<int> a;
  for (int i = 1; i <= 2048; ++i)
    a.push_back(i);

  for (int i = 0; i < 1000; i++) {
    random_shuffle(a.begin(), a.end());
    const auto& v = create_tournament(a);
    assert (second_smaller(v) == 2);
  }

  return 0;
}