Рубрики

Максимум и минимум массива с использованием минимального количества сравнений

Напишите функцию C для возврата минимума и максимума в массиве. Ваша программа должна сделать минимальное количество сравнений.

Прежде всего, как мы возвращаем несколько значений из функции C? Мы можем сделать это, используя структуры или указатели.

Мы создали структуру с именем pair (которая содержит min и max) для возврата нескольких значений.

struct pair 

{

  int min;

  int max;

};  

И объявление функции становится следующим: struct pair getMinMax (int arr [], int n), где arr [] — массив размера n, минимальный и максимальный значения которого необходимы.

МЕТОД 1 (простой линейный поиск)
Инициализируйте значения min и max как минимальные и максимальные из первых двух элементов соответственно. Начиная с 3-го, сравнивайте каждый элемент с max и min и соответственно изменяйте max и min (т. Е. Если элемент меньше min, измените min, иначе, если элемент больше max, измените max, иначе игнорируйте элемент)

С

/ * структура используется для возврата двух значений из minMax () * /
#include<stdio.h>

struct pair 

{

  int min;

  int max;

};  

  

struct pair getMinMax(int arr[], int n)

{

  struct pair minmax;     

  int i;

    

  / * Если есть только один элемент, вернуть как min, так и max одновременно * /

  if (n == 1)

  {

     minmax.max = arr[0];

     minmax.min = arr[0];     

     return minmax;

  }    

  

  / * Если имеется более одного элемента, инициализировать min

      и макс * /

  if (arr[0] > arr[1])  

  {

      minmax.max = arr[0];

      minmax.min = arr[1];

  }  

  else

  {

      minmax.max = arr[1];

      minmax.min = arr[0];

  }    

  

  for (i = 2; i<n; i++)

  {

    if (arr[i] >  minmax.max)      

      minmax.max = arr[i];

    

    else if (arr[i] <  minmax.min)      

      minmax.min = arr[i];

  }

    

  return minmax;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  int arr[] = {1000, 11, 445, 1, 330, 3000};

  int arr_size = 6;

  struct pair minmax = getMinMax (arr, arr_size);

  printf("nMinimum element is %d", minmax.min);

  printf("nMaximum element is %d", minmax.max);

  getchar();

}  

Джава

// Java-программа вышеуказанной реализации

public class GFG {

/ * Class Pair используется для возврата двух значений из getMinMax () * /

    static class Pair {

  

        int min;

        int max;

    }

  

    static Pair getMinMax(int arr[], int n) {

        Pair minmax = new  Pair();

        int i;

  

        / * Если есть только один элемент, вернуть как min, так и max одновременно * /

        if (n == 1) {

            minmax.max = arr[0];

            minmax.min = arr[0];

            return minmax;

        }

  

        / * Если имеется более одного элемента, инициализировать min

    и макс * /

        if (arr[0] > arr[1]) {

            minmax.max = arr[0];

            minmax.min = arr[1];

        } else {

            minmax.max = arr[1];

            minmax.min = arr[0];

        }

  

        for (i = 2; i < n; i++) {

            if (arr[i] > minmax.max) {

                minmax.max = arr[i];

            } else if (arr[i] < minmax.min) {

                minmax.min = arr[i];

            }

        }

  

        return minmax;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[]) {

        int arr[] = {1000, 11, 445, 1, 330, 3000};

        int arr_size = 6;

        Pair minmax = getMinMax(arr, arr_size);

        System.out.printf("\nMinimum element is %d", minmax.min);

        System.out.printf("\nMaximum element is %d", minmax.max);

  

    }

  
}

python3

# Python-программа вышеуказанной реализации

  
# структура используется для возврата двух значений из minMax ()

  

class pair:

    def __init__(self):

        self.min = 0

        self.max = 0

  

def getMinMax(arr: list, n: int) -> pair:

    minmax = pair()

  

    # Если есть только один элемент, верните его как min и max как

    if n == 1:

        minmax.max = arr[0]

        minmax.min = arr[0]

        return minmax

  

    # Если есть более одного элемента, то инициализировать мин

    # и макс

    if arr[0] > arr[1]:

        minmax.max = arr[0]

        minmax.min = arr[1]

    else:

        minmax.max = arr[1]

        minmax.min = arr[0]

  

    for i in range(2, n):

        if arr[i] > minmax.max:

            minmax.max = arr[i]

        elif arr[i] < minmax.min:

            minmax.min = arr[i]

  

    return minmax

  
Код водителя

if __name__ == "__main__":

    arr = [1000, 11, 445, 1, 330, 3000]

    arr_size = 6

    minmax = getMinMax(arr, arr_size)

    print("Minimum element is", minmax.min)

    print("Maximum element is", minmax.max)

  
# Этот код предоставлен
# sanjeev2552

C #

// C # программа вышеуказанной реализации

using System;

  

class GFG 

{

    / * Класс пара используется для возврата

    два значения из getMinMax () * /

    class Pair 

    {

        public int min;

        public int max;

    }

  

    static Pair getMinMax(int []arr, int n)

    {

        Pair minmax = new Pair();

        int i;

  

        / * Если есть только один элемент

        затем верните как min и max оба * /

        if (n == 1)

        {

            minmax.max = arr[0];

            minmax.min = arr[0];

            return minmax;

        }

  

        / * Если есть более одного элемента,

        затем инициализируйте мин и макс * /

        if (arr[0] > arr[1])

        {

            minmax.max = arr[0];

            minmax.min = arr[1];

        

        else

        {

            minmax.max = arr[1];

            minmax.min = arr[0];

        }

  

        for (i = 2; i < n; i++)

        {

            if (arr[i] > minmax.max) 

            {

                minmax.max = arr[i];

            

            else if (arr[i] < minmax.min)

            {

                minmax.min = arr[i];

            }

        }

        return minmax;

    }

  

    // Код драйвера

    public static void Main(String []args) 

    {

        int []arr = {1000, 11, 445, 1, 330, 3000};

        int arr_size = 6;

        Pair minmax = getMinMax(arr, arr_size);

        Console.Write("Minimum element is {0}",

                                   minmax.min);

        Console.Write("\nMaximum element is {0}"

                                     minmax.max);

    }

}

  
// Этот код предоставлен PrinciRaj1992


Выход:

Minimum element is 1
Maximum element is 3000

Сложность времени: O (n)

В этом методе общее количество сравнений составляет 1 + 2 (n-2) в худшем случае и 1 + n — 2 в лучшем случае.
В вышеприведенной реализации наихудший случай возникает, когда элементы сортируются в порядке убывания, а наилучший случай возникает, когда элементы сортируются в порядке возрастания.

МЕТОД 2 (Турнирный метод)
Разделите массив на две части и сравните максимумы и минимумы двух частей, чтобы получить максимум и минимум всего массива.

Pair MaxMin(array, array_size)
   if array_size = 1
      return element as both max and min
   else if arry_size = 2
      one comparison to determine max and min
      return that pair
   else    /* array_size  > 2 */
      recur for max and min of left half
      recur for max and min of right half
      one comparison determines true max of the two candidates
      one comparison determines true min of the two candidates
      return the pair of max and min

Реализация

С

/ * структура используется для возврата двух значений из minMax () * /
#include<stdio.h>

struct pair 

{

  int min;

  int max;

};  

  

struct pair getMinMax(int arr[], int low, int high)

{

  struct pair minmax, mml, mmr;       

  int mid;

    

  / * Если есть только на элементе * /

  if (low == high)

  {

     minmax.max = arr[low];

     minmax.min = arr[low];     

     return minmax;

  }    

    

  / * Если есть два элемента * /

  if (high == low + 1)

  {  

     if (arr[low] > arr[high])  

     {

        minmax.max = arr[low];

        minmax.min = arr[high];

     }  

     else

     {

        minmax.max = arr[high];

        minmax.min = arr[low];

     }  

     return minmax;

  }

    

  / * Если имеется более 2 элементов * /

  mid = (low + high)/2;  

  mml = getMinMax(arr, low, mid);

  mmr = getMinMax(arr, mid+1, high);  

    

  / * сравнить минимумы двух частей * /

  if (mml.min < mmr.min)

    minmax.min = mml.min;

  else

    minmax.min = mmr.min;     

  

  / * сравнить максимумы двух частей * /

  if (mml.max > mmr.max)

    minmax.max = mml.max;

  else

    minmax.max = mmr.max;     

   

  return minmax;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  int arr[] = {1000, 11, 445, 1, 330, 3000};

  int arr_size = 6;

  struct pair minmax = getMinMax(arr, 0, arr_size-1);

  printf("nMinimum element is %d", minmax.min);

  printf("nMaximum element is %d", minmax.max);

  getchar();

}

Джава

// Java-программа вышеуказанной реализации

public class GFG {

/ * Class Pair используется для возврата двух значений из getMinMax () * /

    static class Pair {

  

        int min;

        int max;

    }

  

    static Pair getMinMax(int arr[], int low, int high) {

        Pair minmax = new Pair();

        Pair mml = new Pair();

        Pair mmr = new Pair();

        int mid;

  

        / * Если есть только на элементе * /

        if (low == high) {

            minmax.max = arr[low];

            minmax.min = arr[low];

            return minmax;

        }

  

        / * Если есть два элемента * /

        if (high == low + 1) {

            if (arr[low] > arr[high]) {

                minmax.max = arr[low];

                minmax.min = arr[high];

            } else {

                minmax.max = arr[high];

                minmax.min = arr[low];

            }

            return minmax;

        }

  

        / * Если имеется более 2 элементов * /

        mid = (low + high) / 2;

        mml = getMinMax(arr, low, mid);

        mmr = getMinMax(arr, mid + 1, high);

  

        / * сравнить минимумы двух частей * /

        if (mml.min < mmr.min) {

            minmax.min = mml.min;

        } else {

            minmax.min = mmr.min;

        }

  

        / * сравнить максимумы двух частей * /

        if (mml.max > mmr.max) {

            minmax.max = mml.max;

        } else {

            minmax.max = mmr.max;

        }

  

        return minmax;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[]) {

        int arr[] = {1000, 11, 445, 1, 330, 3000};

        int arr_size = 6;

        Pair minmax = getMinMax(arr, 0, arr_size - 1);

        System.out.printf("\nMinimum element is %d", minmax.min);

        System.out.printf("\nMaximum element is %d", minmax.max);

  

    }

}

C #

// C # реализация подхода

using System;

                      

public class GFG {

/ * Class Pair используется для возврата двух значений из getMinMax () * /

    public class Pair {

   

        public int min;

        public int max;

    }

   

    static Pair getMinMax(int []arr, int low, int high) {

        Pair minmax = new Pair();

        Pair mml = new Pair();

        Pair mmr = new Pair();

        int mid;

   

        / * Если есть только на элементе * /

        if (low == high) {

            minmax.max = arr[low];

            minmax.min = arr[low];

            return minmax;

        }

   

        / * Если есть два элемента * /

        if (high == low + 1) {

            if (arr[low] > arr[high]) {

                minmax.max = arr[low];

                minmax.min = arr[high];

            } else {

                minmax.max = arr[high];

                minmax.min = arr[low];

            }

            return minmax;

        }

   

        / * Если имеется более 2 элементов * /

        mid = (low + high) / 2;

        mml = getMinMax(arr, low, mid);

        mmr = getMinMax(arr, mid + 1, high);

   

        / * сравнить минимумы двух частей * /

        if (mml.min < mmr.min) {

            minmax.min = mml.min;

        } else {

            minmax.min = mmr.min;

        }

   

        / * сравнить максимумы двух частей * /

        if (mml.max > mmr.max) {

            minmax.max = mml.max;

        } else {

            minmax.max = mmr.max;

        }

   

        return minmax;

    }

   

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void Main(String []args) {

        int []arr = {1000, 11, 445, 1, 330, 3000};

        int arr_size = 6;

        Pair minmax = getMinMax(arr, 0, arr_size - 1);

        Console.Write("\nMinimum element is {0}", minmax.min);

        Console.Write("\nMaximum element is {0}", minmax.max);

   

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Minimum element is 1
Maximum element is 3000

Сложность времени: O (n)
Общее количество сравнений: пусть количество сравнений будет T (n). T (n) можно записать следующим образом:
Алгоритмическая парадигма: разделяй и властвуй

             
  T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2  
  T(2) = 1
  T(1) = 0

Если n — степень 2, то мы можем написать T (n) как:

   T(n) = 2T(n/2) + 2 

Решив вышеуказанную рекурсию, мы получим

  T(n)  = 3n/2 -2 

Таким образом, этот подход выполняет 3n / 2 -2 сравнения, если n является степенью 2. И он делает более 3n / 2 -2 сравнения, если n не является степенью 2.

МЕТОД 3 (Сравнить в парах)
Если n нечетно, инициализируйте min и max как первый элемент.
Если n четное, то инициализируйте min и max как минимум и максимум первых двух элементов соответственно.
Для остальных элементов выберите их попарно и сравните их
максимум и минимум с макс и мин соответственно.

С

#include<stdio.h>

  
/ * структура используется для возврата двух значений из minMax () * /

struct pair 

{

  int min;

  int max;

};  

  

struct pair getMinMax(int arr[], int n)

{

  struct pair minmax;     

  int i;  

  

  / * Если массив имеет четное количество элементов, то

    инициализировать первые два элемента как минимум и

    максимум * /

  if (n%2 == 0)

  {         

    if (arr[0] > arr[1])     

    {

      minmax.max = arr[0];

      minmax.min = arr[1];

    }  

    else

    {

      minmax.min = arr[0];

      minmax.max = arr[1];

    }

    i = 2;  / * установить индекс запуска для цикла * /

  }  

  

   / * Если массив имеет нечетное количество элементов, то

    инициализировать первый элемент как минимум и

    максимум * / 

  else

  {

    minmax.min = arr[0];

    minmax.max = arr[0];

    i = 1;  / * установить индекс запуска для цикла * /

  }

    

  / * В цикле while выбираем элементы в паре и

     сравните пару с макс и мин до сих пор * /    

  while (i < n-1)  

  {          

    if (arr[i] > arr[i+1])          

    {

      if(arr[i] > minmax.max)        

        minmax.max = arr[i];

      if(arr[i+1] < minmax.min)          

        minmax.min = arr[i+1];        

    

    else         

    {

      if (arr[i+1] > minmax.max)        

        minmax.max = arr[i+1];

      if (arr[i] < minmax.min)          

        minmax.min = arr[i];        

    }        

    i += 2; / * Увеличить индекс на 2 как два

               элементы обрабатываются в цикле * /

  }            

  

  return minmax;

}    

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  int arr[] = {1000, 11, 445, 1, 330, 3000};

  int arr_size = 6;

  struct pair minmax = getMinMax (arr, arr_size);

  printf("nMinimum element is %d", minmax.min);

  printf("nMaximum element is %d", minmax.max);

  getchar();

}

Джава

// Java-программа вышеуказанной реализации

public class GFG {

  
/ * Class Pair используется для возврата двух значений из getMinMax () * /

    static class Pair {

  

        int min;

        int max;

    }

  

    static Pair getMinMax(int arr[], int n) {

        Pair minmax = new Pair();

        int i;

        / * Если массив имеет четное количество элементов, то

    инициализировать первые два элемента как минимум и

    максимум * /

        if (n % 2 == 0) {

            if (arr[0] > arr[1]) {

                minmax.max = arr[0];

                minmax.min = arr[1];

            } else {

                minmax.min = arr[0];

                minmax.max = arr[1];

            }

            i = 2;

            / * установить индекс запуска для цикла * /

        } / * Если массив имеет нечетное количество элементов, то

    инициализировать первый элемент как минимум и

    максимум * / else {

            minmax.min = arr[0];

            minmax.max = arr[0];

            i = 1;

            / * установить индекс запуска для цикла * /

        }

  

        / * В цикле while выбираем элементы в паре и

     сравните пару с макс и мин до сих пор * /

        while (i < n - 1) {

            if (arr[i] > arr[i + 1]) {

                if (arr[i] > minmax.max) {

                    minmax.max = arr[i];

                }

                if (arr[i + 1] < minmax.min) {

                    minmax.min = arr[i + 1];

                }

            } else {

                if (arr[i + 1] > minmax.max) {

                    minmax.max = arr[i + 1];

                }

                if (arr[i] < minmax.min) {

                    minmax.min = arr[i];

                }

            }

            i += 2;

            / * Увеличить индекс на 2 как два

               элементы обрабатываются в цикле * /

        }

  

        return minmax;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[]) {

        int arr[] = {1000, 11, 445, 1, 330, 3000};

        int arr_size = 6;

        Pair minmax = getMinMax(arr, arr_size);

        System.out.printf("\nMinimum element is %d", minmax.min);

        System.out.printf("\nMaximum element is %d", minmax.max);

  

    }

}

python3

# Python3 программа вышеуказанной реализации

def getMinMax(arr):

      

    n = len(arr)

      

    # Если массив имеет четное количество элементов, то

    # инициализировать первые два элемента как минимум

    # и максимум

    if(n % 2 == 0):

        mx = max(arr[0], arr[1])

        mn = min(arr[0], arr[1])

          

        # установить начальный индекс для цикла

        i = 2

          

    # Если массив имеет нечетное количество элементов, то

    # инициализировать первый элемент как минимум

    # и максимум

    else:

        mx = mn = arr[0]

          

        # установить начальный индекс для цикла

        i = 1

          

    # В цикле while выберите элементы в паре и

    # сравните пару с макс и мин до сих пор

    while(i < n - 1):

        if arr[i] < arr[i + 1]:

            mx = max(mx, arr[i + 1])

            mn = min(mn, arr[i])

        else:

            mx = max(mx, arr[i])

            mn = min(mn, arr[i + 1])

              

        # Увеличить индекс на 2 как два

        # элементы обрабатываются в цикле

        i += 2

      

    return (mx, mn)

      
Код водителя

if __name__ =='__main__':

      

    arr = [1000, 11, 445, 1, 330, 3000]

    mx, mn = getMinMax(arr)

    print("Minimum element is", mn)

    print("Maximum element is", mx)

      
# Этот код предоставлен Kaustav

C #

// C # программа вышеуказанной реализации

using System;

      

class GFG 

{

  

    / * Класс пара используется для возврата

       два значения из getMinMax () * /

    public class Pair 

    {

        public int min;

        public int max;

    }

  

    static Pair getMinMax(int []arr, int n)

    {

        Pair minmax = new Pair();

        int i;

          

        / * Если массив имеет четное количество элементов

        затем инициализировать первые два элемента

        как минимум и максимум * /

        if (n % 2 == 0) 

        {

            if (arr[0] > arr[1])

            {

                minmax.max = arr[0];

                minmax.min = arr[1];

            

            else

            {

                minmax.min = arr[0];

                minmax.max = arr[1];

            }

            i = 2;

        }

          

        / * установить индекс запуска для цикла * /

        / * Если массив имеет нечетное количество элементов, то

        инициализировать первый элемент как минимум и

        максимум * / 

        else 

        {

            minmax.min = arr[0];

            minmax.max = arr[0];

            i = 1;

            / * установить индекс запуска для цикла * /

        }

  

        / * В цикле while выбираем элементы в паре и

        сравните пару с макс и мин до сих пор * /

        while (i < n - 1) 

        {

            if (arr[i] > arr[i + 1]) 

            {

                if (arr[i] > minmax.max) 

                {

                    minmax.max = arr[i];

                }

                if (arr[i + 1] < minmax.min)

                {

                    minmax.min = arr[i + 1];

                }

            

            else

            {

                if (arr[i + 1] > minmax.max)

                {

                    minmax.max = arr[i + 1];

                }

                if (arr[i] < minmax.min)

                {

                    minmax.min = arr[i];

                }

            }

            i += 2;

              

            / * Увеличить индекс на 2 как два

            элементы обрабатываются в цикле * /

        }

        return minmax;

    }

  

    // Код драйвера

    public static void Main(String []args) 

    {

        int []arr = {1000, 11, 445, 1, 330, 3000};

        int arr_size = 6;

        Pair minmax = getMinMax(arr, arr_size);

        Console.Write("Minimum element is {0}",

                                   minmax.min);

        Console.Write("\nMaximum element is {0}"

                                     minmax.max);

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Minimum element is 1
Maximum element is 3000

Сложность времени: O (n)

Общее количество сравнений: отличается для четных и нечетных n, см. Ниже:

       If n is odd:    3*(n-1)/2  
       If n is even:   1 Initial comparison for initializing min and max, 
                           and 3(n-2)/2 comparisons for rest of the elements  
                      =  1 + 3*(n-2)/2 = 3n/2 -2

Второй и третий подходы делают равное количество сравнений, когда n является степенью 2.

В общем, метод 3 кажется лучшим.

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в вышеупомянутых программах / алгоритмах или лучший способ решить ту же проблему.

Рекомендуемые посты:

Максимум и минимум массива с использованием минимального количества сравнений

0.00 (0%) 0 votes