Рубрики

Лидеры в массиве

Напишите программу для печати всех ЛИДЕРОВ в массиве. Элемент является лидером, если он больше, чем все элементы с правой стороны. И самый правый элемент — это всегда лидер. Например, в массиве {16, 17, 4, 3, 5, 2}, лидерами являются 17, 5 и 2.

Пусть входной массив будет arr [], а размер массива будет размером .

Способ 1 (простой)
Используйте две петли. Внешний цикл работает от 0 до размера — 1 и один за другим выбирает все элементы слева направо. Внутренний цикл сравнивает выбранный элемент со всеми элементами с правой стороны. Если выбранный элемент больше, чем все элементы с правой стороны, то выбранный элемент является лидером.

C ++

#include<iostream>

using namespace std;

  
/ * C ++ Функция для печати лидеров в массиве * /

void printLeaders(int arr[], int size)

{

    for (int i = 0; i < size; i++)

    {

        int j;

        for (j = i+1; j < size; j++)

        {

            if (arr[i] <= arr[j])

                break;

        }    

        if (j == size) // цикл не прерывался

            cout << arr[i] << " ";

  }

}

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

int main()

{

    int arr[] = {16, 17, 4, 3, 5, 2};

    int n = sizeof(arr)/sizeof(arr[0]);

    printLeaders(arr, n);

    return 0;

}

Джава

class LeadersInArray 

{

    / * Java функция для печати лидеров в массиве * /

    void printLeaders(int arr[], int size) 

    {

        for (int i = 0; i < size; i++) 

        {

            int j;

            for (j = i + 1; j < size; j++) 

            {

                if (arr[i] <= arr[j])

                    break;

            }

            if (j == size) // цикл не прерывался

                System.out.print(arr[i] + " ");

        }

    }

  

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

    public static void main(String[] args) 

    {

        LeadersInArray lead = new LeadersInArray();

        int arr[] = new int[]{16, 17, 4, 3, 5, 2};

        int n = arr.length;

        lead.printLeaders(arr, n);

    }

}

питон

# Python Функция для печати лидеров в массиве

  

def printLeaders(arr,size):

      

    for i in range(0, size):

        for j in range(i+1, size):

            if arr[i]<=arr[j]:

                break

        if j == size-1: # Если цикл не прерывался

            print arr[i],

  
# Функция драйвера

arr=[16, 17, 4, 3, 5, 2]

printLeaders(arr, len(arr))

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

C #

// C # программа для печати
// лидеры в массиве

using System;

class GFG 

{

    void printLeaders(int []arr, 

                      int size) 

    {

        for (int i = 0; i < size; i++) 

        {

            int j;

            for (j = i + 1; j < size; j++) 

            {

                if (arr[i] <= arr[j])

                    break;

            }

              

            // цикл не прерывался

            if (j == size) 

                Console.Write(arr[i] + " ");

        }

    }

  

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

    public static void Main() 

    {

        GFG lead = new GFG();

        int []arr = new int[]{16, 17, 4, 3, 5, 2};

        int n = arr.Length;

        lead.printLeaders(arr, n);

    }

}

  
// Этот код предоставлен
// Akanksha Rai (Abby_akku)

PHP

<?php
// PHP функция для печати
// лидеры в массиве

function printLeaders($arr, $size)

{

    for ($i = 0; $i < $size; $i++)

    {

        for ($j = $i + 1;

             $j < $size; $j++)

        {

            if ($arr[$i] <= $arr[$j])

                break;

        

          

        // цикл не прерывался

        if ($j == $size)

            echo($arr[$i] . " "); 

        }

}

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

$arr = array(16, 17, 4, 3, 5, 2);

$n = sizeof($arr);

printLeaders($arr, $n);

      
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

17 5 2

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

Способ 2 (Сканирование справа)
Просканируйте все элементы справа налево в массиве и отслеживайте максимум до сих пор. Когда максимум меняет свое значение, выведите его.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

#include <iostream>

using namespace std;

  
/ * C ++ Функция для печати лидеров в массиве * /

void printLeaders(int arr[], int size)

{

    int max_from_right =  arr[size-1];

  

    / * Самый правый элемент всегда лидер * /

    cout << max_from_right << " ";

      

    for (int i = size-2; i >= 0; i--)

    {

        if (max_from_right < arr[i])

        {           

            max_from_right = arr[i];

            cout << max_from_right << " ";

        }

    }    

}

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

int main()

{

    int arr[] = {16, 17, 4, 3, 5, 2};

    int n = sizeof(arr)/sizeof(arr[0]);

    printLeaders(arr, n);

    return 0;

}    

Джава

class LeadersInArray 

{

    / * Java функция для печати лидеров в массиве * /

    void printLeaders(int arr[], int size)

    {

        int max_from_right =  arr[size-1];

   

        / * Самый правый элемент всегда лидер * /

        System.out.print(max_from_right + " ");

       

        for (int i = size-2; i >= 0; i--)

        {

            if (max_from_right < arr[i])

            {           

            max_from_right = arr[i];

            System.out.print(max_from_right + " ");

            }

        }    

    }

  

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

    public static void main(String[] args) 

    {

        LeadersInArray lead = new LeadersInArray();

        int arr[] = new int[]{16, 17, 4, 3, 5, 2};

        int n = arr.length;

        lead.printLeaders(arr, n);

    }

}

питон

# Python функция для печати лидеров в массиве

def printLeaders(arr, size):

     

    max_from_right = arr[size-1]   

    print max_from_right,    

    for i in range( size-2, -1, -1):        

        if max_from_right < arr[i]:            

            print arr[i],

            max_from_right = arr[i]

          
# Функция драйвера

arr = [16, 17, 4, 3, 5, 2]

printLeaders(arr, len(arr))

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

C #

// C # программа для поиска лидеров в массиве

using System;

  

class LeadersInArray {

      

    // C # Функция для печати лидеров

    // в массиве

    void printLeaders(int []arr, int size)

    {

        int max_from_right = arr[size - 1];

  

        // Самый правый элемент всегда лидер

        Console.Write(max_from_right +" ");

      

        for (int i = size - 2; i >= 0; i--)

        {

            if (max_from_right < arr[i])

            {     

                max_from_right = arr[i];

                Console.Write(max_from_right +" ");

            }

        

    }

  

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

    public static void Main(String[] args) 

    {

        LeadersInArray lead = new LeadersInArray();

        int []arr = new int[]{16, 17, 4, 3, 5, 2};

        int n = arr.Length;

        lead.printLeaders(arr, n);

    }

}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

PHP

<?php
// PHP функция для печати
// лидеры в массиве

function printLeaders(&$arr, $size)

{

    $max_from_right = $arr[$size - 1];

  

    // Самый правый элемент

    // всегда лидер

    echo($max_from_right);

    echo(" ");

      

    for ($i = $size - 2; 

         $i >= 0; $i--)

    {

        if ($max_from_right < $arr[$i])

        {         

            $max_from_right = $arr[$i];

            echo($max_from_right);

            echo(" ");

        }

    

}

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

$arr = array(16, 17, 4, 3, 5, 2);

$n = sizeof($arr);

printLeaders($arr, $n);

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

2 5 17


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

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

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

Лидеры в массиве

0.00 (0%) 0 votes