Найти второе по величине число в массиве при сравнении n + log₂ (n) -2

Ответ 1

• Начните с сравнения элементов массива n элементов в нечетных и четных положениях и определения наибольшего элемента каждой пары. Этот шаг требует n/2 сравнений. Теперь у вас есть только n/2 элемента. Продолжайте парные сравнения, чтобы получить элементы n/4, n/8,.... Остановитесь, когда найден самый большой элемент. Для этого шага требуется общее сравнение n/2 + n/4 + n/8 +... + 1 = n-1.
• На предыдущем шаге наибольший элемент сразу сравнивался с log₂ (n) другими элементами. Вы можете определить самый большой из этих элементов в сравнении log₂ (n) -1. Это будет вторым по величине числом в массиве.

Пример: массив из 8 чисел [10,9,5,4,11,100,120,110].

Сравнения на уровне 1: [10,9] → 10 [5,4] → 5, [11,100] → 100, [120,110] → 120.

Сравнения на уровне 2: [10,5] → 10 [100, 120] → 120.

Сравнение на уровне 3: [10, 120] → 120.

Максимум 120. Он был немедленно сравнен с: 10 (на уровне 3), 100 (на уровне 2), 110 (на уровне 1).

Шаг 2 должен найти максимум 10, 100 и 110. Это 110. Это второй по величине элемент.

Ответ 2

проблема заключается в следующем: скажем, на уровне сравнения 1, алгоритм должен помнить весь элемент массива, потому что наибольший пока не известен, затем, во-вторых, наконец, третий. продолжая отслеживать этот элемент с помощью присваивания, вызывается дополнительное назначение значений, а позже, когда известно самое большое, вам также нужно учитывать отслеживание. В результате это не будет значительно быстрее, чем простой алгоритм сравнения 2N-2. Более того, поскольку код более сложный, вам также нужно подумать о возможном времени отладки.
например: в PHP, время RUNNING для сравнения и назначение значений примерно равно: Сравнение: (11-19) для присвоения значения: 16.

Ответ 3

nlogn реализация

      public class Test {
           public static void main(String...args){
              int arr[] = new int[]{1,2,2,3,3,4,9,5, 100 , 101, 1, 2, 1000, 102, 2,2,2};
              System.out.println(getMax(arr, 0, 16));
           }

        public static Holder getMax(int[] arr, int start, int end){
           if (start == end)
             return new Holder(arr[start], Integer.MIN_VALUE);
        else {
          int mid = ( start + end ) / 2;
          Holder l = getMax(arr, start, mid);
          Holder r = getMax(arr, mid + 1, end);

          if (l.compareTo(r) > 0 )
            return new Holder(l.high(), r.high() > l.low() ? r.high() : l.low());
          else
            return new Holder(r.high(), l.high() > r.low() ? l.high(): r.low());
        }
      }

    static class Holder implements Comparable<Holder> {
      private int low, high;
      public Holder(int r, int l){low = l; high = r;}

    public String toString(){
      return String.format("Max: %d, SecMax: %d", high, low);
    }

    public int compareTo(Holder data){
      if (high == data.high)
        return 0;

      if (high > data.high)
        return 1;
      else
        return -1;
    }

    public int high(){
      return high;
    }
    public int low(){
      return low;
    }
  }

}

Ответ 4

Я реализовал этот алгоритм в Java, на который ответил @Evgeny Kluev. Общее сравнение: n + log2 (n) -2. Существует также хорошая рекомендация: http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec03.349.pdf. Это похоже на верхний проголосовавший алгоритм. Надеюсь, мое решение будет полезно. Спасибо.

public class op1 {

private static int findSecondRecursive(int n, int[] A){
    int[] firstCompared = findMaxTournament(0, n-1, A); //n-1 comparisons;
    int[] secondCompared = findMaxTournament(2, firstCompared[0]-1, firstCompared); //log2(n)-1 comparisons.
    //Total comparisons: n+log2(n)-2;
    return secondCompared[1];
}

private static int[] findMaxTournament(int low, int high, int[] A){
    if(low == high){
        int[] compared = new int[2];
        compared[0] = 2;
        compared[1] = A[low];
        return compared;
    }
    int[] compared1 = findMaxTournament(low, (low+high)/2, A);
    int[] compared2 = findMaxTournament((low+high)/2+1, high, A);
    if(compared1[1] > compared2[1]){
        int k = compared1[0] + 1;
        int[] newcompared1 = new int[k];
        System.arraycopy(compared1, 0, newcompared1, 0, compared1[0]);
        newcompared1[0] = k;
        newcompared1[k-1] = compared2[1];
        return newcompared1;
    }
    int k = compared2[0] + 1;
    int[] newcompared2 = new int[k];
    System.arraycopy(compared2, 0, newcompared2, 0, compared2[0]);
    newcompared2[0] = k;
    newcompared2[k-1] = compared1[1];
    return newcompared2;
}

private static void printarray(int[] a){
    for(int i:a){
        System.out.print(i + " ");
    }
    System.out.println();
}

public static void main(String[] args) {
    //Demo.
    System.out.println("Origial array: ");
    int[] A = {10,4,5,8,7,2,12,3,1,6,9,11};
    printarray(A);
    int secondMax = findSecondRecursive(A.length,A);
    Arrays.sort(A);
    System.out.println("Sorted array(for check use): ");
    printarray(A);
    System.out.println("Second largest number in A: " + secondMax);
}

}

Ответ 5

I shall give some examples for better understanding. :
example 1 :
>12 56 98 12 76 34 97 23
>>(12 56) (98 12) (76 34) (97 23)
>>> 56 98 76 97 
>>>> (56 98) (76 97)
>>>>> 98 97
>>>>>> 98   

The largest element is 98

Now compare with lost ones of the largest element 98. 97 will be the second largest.

Ответ 6

Почему бы не использовать этот алгоритм хэширования для заданного массива [n]? Он работает c * n, где c - постоянное время проверки и хэша. И это делает n сравнений.

    int first = 0;
    int second = 0;
    for(int i = 0; i < n; i++) {
        if(array[i] > first) {
            second = first;
            first = array[i];
        }
    }

Или я просто не понимаю вопроса...

Ответ 7

В Python2.7: Следующий код работает в O (nlog log n) для дополнительной сортировки. Любая оптимизация?

def secondLargest(testList):
    secondList = []
    # Iterate through the list
    while(len(testList) > 1):
        left = testList[0::2]
        right = testList[1::2]

        if (len(testList) % 2 == 1):
            right.append(0)

        myzip = zip(left,right)
        mymax = [ max(list(val)) for val in myzip ]
        myzip.sort()
        secondMax = [x for x in myzip[-1] if x != max(mymax)][0]

        if (secondMax != 0 ):
            secondList.append(secondMax)
        testList = mymax

    return max(secondList)

Ответ 8

public static int FindSecondLargest(int[] input)
        {
            Dictionary<int, List<int>> dictWinnerLoser = new Dictionary<int, List<int>>();//Keeps track of loosers with winners
            List<int> lstWinners = null;
            List<int> lstLoosers = null;

            int winner = 0;
            int looser = 0;

            while (input.Count() > 1)//Runs till we get max in the array
            {
                lstWinners = new List<int>();//Keeps track of winners of each run, as we have to run with winners of each run till we get one winner

                for (int i = 0; i < input.Count() - 1; i += 2)
                {
                    if (input[i] > input[i + 1])
                    {
                        winner = input[i];
                        looser = input[i + 1];
                    }
                    else
                    {
                        winner = input[i + 1];
                        looser = input[i];
                    }

                    lstWinners.Add(winner);


                    if (!dictWinnerLoser.ContainsKey(winner))
                    {
                        lstLoosers = new List<int>();
                        lstLoosers.Add(looser);
                        dictWinnerLoser.Add(winner, lstLoosers);
                    }
                    else
                    {
                        lstLoosers = dictWinnerLoser[winner];
                        lstLoosers.Add(looser);
                        dictWinnerLoser[winner] = lstLoosers;
                    }
                }

                input = lstWinners.ToArray();//run the loop again with winners
            }

            List<int> loosersOfWinner = dictWinnerLoser[input[0]];//Gives all the elemetns who lost to max element of array, input array now has only one element which is actually the max of the array

            winner = 0;

            for (int i = 0; i < loosersOfWinner.Count(); i++)//Now max in the lossers of winner will give second largest
            {
                if (winner < loosersOfWinner[i])
                {
                    winner = loosersOfWinner[i];
                }
            }

            return winner;
        }