Нахождение второго по величине числа в массиве

Question

Мне сложно понять логику метода, чтобы найти второе по величине число в массиве. Используемый метод состоит в том, чтобы найти самое высокое в массиве, но меньше, чем предыдущее самое высокое (которое уже было найдено). То, что я до сих пор не могу понять, это то, почему || highest_score == second_highest необходимо. Например, я ввожу три числа: 98, 56, 3. Без него как наивысшее, так и второе наивысшее будет 98. Пожалуйста, объясните.

int second highest = score[0];  
if (score[i] > second_highest && score[i] < highest_score || highest_score == second_highest)   
    second_highest = score[i];

Answer 1

Вы также можете найти самое большое и третье по величине количество несортированных массивов.

 public class ThirdLargestNumber {
        public static void main(String[] args) {
            int arr[] = { 220, 200, 100, 100, 300, 600, 50, 5000, 125, 785 };
            int first = 0, second = 0, third = 0, firstTemp = 0, secondTemp = 0;
            for (int i = 0; i <= 9 /*
                                     * Length of array-1. You can use here length
                                     * property of java array instead of hard coded
                                     * value
                                     */; i++) {
                if (arr[i] == first) {
                    continue;
                }
                if (arr[i] > first) {
                    firstTemp = first;
                    secondTemp = second;
                    first = arr[i];
                    second = firstTemp;
                    if (secondTemp > third) {
                        third = secondTemp;
                    }
                } else {
                    if ((arr[i] == second) || (arr[i]) == first) {
                        continue;
                    }
                    if ((arr[i] > second) && (arr[i]) < first) {
                        secondTemp = second;
                        second = arr[i];
                        if (secondTemp > third) {
                            third = secondTemp;
                        }
                    } else {
                        if (arr[i] > third) {
                            third = arr[i];
                        }
                    }
                }
            }
            // System.out.println("Third largest number: " + third);
            System.out.println("Second largest number: " + second);
            // System.out.println("Largest number: " + first);
        }
    }

Answer 2

Если этот вопрос задан интервьюером, НЕ ИСПОЛЬЗУЙТЕ метод сортировки или не используйте встроенные методы, такие как Arrays.sort или Collection.sort. Цель этих вопросов состоит в том, насколько оптимально ваше решение с точки зрения производительности, поэтому лучшим вариантом будет просто реализовать свою собственную логику с реализацией O (n-1). Приведенный ниже код предназначен исключительно для начинающих, а не для опытных парней.

  public void printLargest(){


    int num[] ={ 900,90,6,7,5000,4,60000,20,3};

    int largest = num[0];

    int secondLargest = num[1];

    for (int i=1; i<num.length; i++)
    {
        if(largest < num[i])
        {
            secondLargest = largest;
            largest = num[i];


        }
        else if(secondLargest < num[i]){
            secondLargest = num[i];
        }
    }
    System.out.println("Largest : " +largest);
    System.out.println("Second Largest : "+secondLargest);
}

Answer 3

import java.util.Scanner;

public class SecondLargest {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter size of array : ");
        int n = sc.nextInt();
        int ar[] = new int[n];
        for(int i=0;i<n;i++)
        {
            System.out.print("Enter value for array : ");
            ar[i] = sc.nextInt();
        }
        int m=ar[0],m2=ar[0];
        for(int i=0;i<n;i++)
        {
            if(ar[i]>m)
                m=ar[i];
        }
        for(int i=0;i<n;i++)
        {
            if(ar[i]>m2 && ar[i]<m)
                m2=ar[i];
        }
        System.out.println("Second largest : "+m2);
        sc.close();
    }
}

Answer 4

Проблема: Проблема в том, чтобы получить второй по величине элемент массива.

Наблюдение: Второе по величине число определяется как число, которое имеет минимальную разницу при вычитании из максимального элемента в массиве.

Решение: Это двухпроходное решение. Первый проход - найти максимальное количество. Второй проход - найти элемент, который имеет минимальную разницу с максимальным элементом по сравнению с другими элементами массива. Пример: в массиве [2, 3, 6, 6, 5] максимум = 6 и второй максимум = 5, поскольку он имеет минимальную разницу с максимальным элементом 6 - 5 = 1, решение для второго по величине = 5

function printSecondMax(myArray) {
  var x, max = myArray[0];
  // Find maximum element 
  for(x in myArray){
     if(max < myArray[x]){
        max = myArray[x];
     }
  }
  var secondMax = myArray[0], diff = max - secondMax;
  // Find second max, an element that has min diff with the max
  for(x in myArray){
    if(diff != 0 && (max - myArray[x]) != 0 && diff > (max - myArray[x])){
        secondMax = myArray[x];
        diff = max - secondMax;
    }
  }
  console.log(secondMax);
}

Сложность: O (n), это самый простой способ сделать это.

Чтобы найти максимальный элемент еще эффективнее, можно заглянуть в max heap , вызов max-heapify займет O (log n) времени, чтобы найти максимум, а затем всплывающий верхний элемент дает максимум. Чтобы получить второй максимум, max-heapify после всплывающего окна и продолжайте всплывать, пока не получите число, которое меньше максимального. Это будет второй максимум. Это решение имеет O (n log n) сложности.

Answer 5

public class SecondLargestNumber
{
  public static void main(String[] args)
  {
    int[] var={-11,-11,-11,-11,115,-11,-9};
    int largest = 0;
    int secLargest = 0;
    if(var.length == 1)
    {
      largest = var[0];
      secLargest = var[0];
    }
    else if(var.length > 1)
    {
      largest= var[0];
      secLargest = var[1];
      for(int i=1;i<var.length;i++)
      {
        if(secLargest!=largest)
        {
          if(var[i]>largest)
          { 
            secLargest = largest;
            largest = var[i];
          }
          else if(var[i]>secLargest && var[i] != largest)
          {
            secLargest= var[i];
          }
        }
        else
        {
          if(var[i]>largest)
          {
           secLargest = largest;
           largest = var[i];
          }
          else
          {
           secLargest = var[i];
          }
       }
    }
  }

    System.out.println("Largest: "+largest+" Second Largest: "+secLargest);
  }
}

Answer 6

открытый класс SecondHighInIntArray {

public static void main(String[] args) {
    int[] intArray=new int[]{2,2,1};
            //{2,2,1,12,3,7,9,-1,-5,7};
    int secHigh=findSecHigh(intArray);
    System.out.println(secHigh);
}

private static int findSecHigh(int[] intArray) {

    int highest=Integer.MIN_VALUE;
    int sechighest=Integer.MIN_VALUE;
    int len=intArray.length;
    for(int i=0;i<len;i++)
    {
        if(intArray[i]>highest)
        {
            sechighest=highest;
            highest=intArray[i];
            continue;
        }

        if(intArray[i]<highest && intArray[i]>sechighest)
        {
            sechighest=intArray[i];
            continue;
        }


    }
    return sechighest;
}

}

Answer 7

private static int SecondBiggest(int[] vector)
{
    if (vector == null)
    {
        throw new ArgumentNullException("vector");
    }
    if (vector.Length < 2)
    {
        return int.MinValue;
    }

    int max1 = vector[0];
    int max2 = vector[1];
    for (int i = 2; i < vector.Length; ++i)
    {
        if (max1 > max2 && max1 != vector[i])
        {
            max2 = Math.Max(max2, vector[i]);
        }
        else if (max2 != vector[i])
        {
            max1 = Math.Max(max1, vector[i]);
        }
    }
    return Math.Min(max1, max2);
}

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

Answer 8

Использовать следующую функцию
`

public static int secHigh(int arr[]){
            int firstHigh = 0,secHigh = 0;
            for(int x: arr){
                if(x > firstHigh){
                    secHigh = firstHigh;
                    firstHigh = x;
                }else if(x > secHigh){
                    secHigh = x;
                }
            }
            return secHigh;
        }

вызов функции

int secondHigh = secHigh(arr);

Answer 9

Это мой ответ во время сложности C, O (N). Передайте массив только один раз, только три переменные. Решение очень интуитивное и простое для понимания.

 #include <stdio.h>

    int second(int arr[],int size)
    {
        int i, max , secondmax;

        if (arr[0] > arr[1]){
            max = arr[0];
            secondmax = arr[1];
        } else {
            max = arr[1];
            secondmax = arr[0];
        }
        for (i = 2; i < size; i++)
        {
            if ((arr[i] < max) && (arr[i] < secondmax)) {
                continue;
            }
            if ((arr[i] < max) && (arr[i] > secondmax)) {
                secondmax = arr[i];
                continue;
            }
            if ((arr[i] > max)) {
                secondmax = max;
                max = arr[i];
                continue;
            }
        }
        return secondmax;
    }
    void main()
    {
        int arr[] = { 1,10,5,7};
        int size = sizeof(arr) / sizeof(arr[0]);
        int secondmax = second(arr,size);
        printf("%d \n\n", secondmax);
    }

Answer 10

public void findMax(int a[]) {
    int large = Integer.MIN_VALUE;
    int secondLarge = Integer.MIN_VALUE;
    for (int i = 0; i < a.length; i++) {
        if (large < a[i]) {
            secondLarge = large;
            large = a[i];
        } else if (a[i] > secondLarge) {
            if (a[i] != large) {
                secondLarge = a[i];
            }
        }
    }
    System.out.println("Large number " + large + " Second Large  number " + secondLarge);
}

Приведенный выше код был протестирован с целочисленными массивами, имеющими повторяющиеся записи, отрицательные значения. Наибольшее число и второе по величине число извлекаются за один проход. Этот код завершается ошибкой только в том случае, если массив содержит несколько копий с одинаковым номером, например {8,8,8,8}, или с одним номером.