Я знаю, что это старый вопрос, но вот моя попытка решить его, используя алгоритм турнира.Это похоже на решение, используемое @sdcvvc, но я использую двумерный массив для хранения элементов.
Чтобы все работало, есть два предположения:
1) количество элементов в массивеявляется степенью 2
2) в массиве нет дубликатов
Весь процесс состоит из двух этапов:
1. построение двумерного массива путем сравнения двух на два элемента.Первая строка в 2D-массиве будет представлять собой весь входной массив.Следующая строка содержит результаты сравнений предыдущей строки.Мы продолжаем сравнение на вновь построенном массиве и продолжаем строить 2D-массив, пока не будет достигнут массив только из одного элемента (самый большой).
2. у нас есть 2D-массив, где последняя строка содержит только один элемент: самый большойодин.Мы продолжаем идти снизу вверх, в каждом массиве находим элемент, который был «побит» наибольшим, и сравниваем его с текущим «вторым по величине» значением.Чтобы найти элемент, побитый наибольшим, и чтобы избежать O (n) сравнений, мы должны сохранить индекс самого большого элемента в предыдущей строке.Таким образом, мы можем легко проверить соседние элементы.На любом уровне (выше корневого уровня) соседние элементы получаются как:
leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,
, где rootIndex - это индекс самого большого (корневого) элемента на предыдущем уровне.
Я знаюВопрос требует C ++, но вот моя попытка решить его в Java.(Я использовал списки вместо массивов, чтобы избежать беспорядочного изменения размера массива и / или ненужных вычислений размера массива)
public static Integer findSecondLargest(List<Integer> list) {
if (list == null) {
return null;
}
if (list.size() == 1) {
return list.get(0);
}
List<List<Integer>> structure = buildUpStructure(list);
System.out.println(structure);
return secondLargest(structure);
}
public static List<List<Integer>> buildUpStructure(List<Integer> list) {
List<List<Integer>> newList = new ArrayList<List<Integer>>();
List<Integer> tmpList = new ArrayList<Integer>(list);
newList.add(tmpList);
int n = list.size();
while (n>1) {
tmpList = new ArrayList<Integer>();
for (int i = 0; i<n; i=i+2) {
Integer i1 = list.get(i);
Integer i2 = list.get(i+1);
tmpList.add(Math.max(i1, i2));
}
n/= 2;
newList.add(tmpList);
list = tmpList;
}
return newList;
}
public static Integer secondLargest(List<List<Integer>> structure) {
int n = structure.size();
int rootIndex = 0;
Integer largest = structure.get(n-1).get(rootIndex);
List<Integer> tmpList = structure.get(n-2);
Integer secondLargest = Integer.MIN_VALUE;
Integer leftAdjacent = -1;
Integer rightAdjacent = -1;
for (int i = n-2; i>=0; i--) {
rootIndex*=2;
tmpList = structure.get(i);
leftAdjacent = tmpList.get(rootIndex);
rightAdjacent = tmpList.get(rootIndex+1);
if (leftAdjacent.equals(largest)) {
if (rightAdjacent > secondLargest) {
secondLargest = rightAdjacent;
}
}
if (rightAdjacent.equals(largest)) {
if (leftAdjacent > secondLargest) {
secondLargest = leftAdjacent;
}
rootIndex=rootIndex+1;
}
}
return secondLargest;
}