Рубрики

Благородные целые числа в массиве (количество больших элементов равно значению)

Учитывая массив arr [], найдите в нем целое число Noble. Целое число x называется Noble в arr [], если число целых чисел больше x равно x. Если есть много благородных целых чисел, верните любое из них. Если нет, вернуть -1.

Примеры :

Input  : [7, 3, 16, 10]
Output : 3  
Number of integers greater than 3
is three.

Input  : [-1, -9, -2, -78, 0]
Output : 0
Number of integers greater than 0
is zero.

Метод 1 (грубая сила)
Итерация по массиву. Для каждого элемента arr [i] найдите количество элементов больше, чем arr [i].

CPP

// C ++ программа для поиска благородных элементов
// в массиве.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает Благородное целое число, если присутствует,
// иначе возвращает -1.

int nobleInteger(int arr[], int size)

{

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

    {

        int count = 0;

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

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

                count++;

                  

        // Если количество больших элементов

        // равно arr [i]

        if (count == arr[i])

            return arr[i];

    }

      

    return -1;

}

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

int main()

{

    int arr[] = {10, 3, 20, 40, 2};

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

    int res = nobleInteger(arr, size);

      

    if (res != -1)

        cout<<"The noble integer is "<< res;

    else

        cout<<"No Noble Integer Found";

}

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

Джава

// Java программа для поиска благородных элементов
// в массиве.

import java.util.ArrayList;

  

class GFG {

      

    // Возвращает Благородное целое число, если присутствует,

    // иначе возвращает -1.

    public static int nobleInteger(int arr[])

    {

        int size = arr.length;

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

        {

            int count = 0;

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

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

                    count++;

  

            // Если количество больших элементов

            // равно arr [i]

            if (count == arr[i])

                return arr[i];

        }

        return -1;

    }

  

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

    public static void main(String args[])

    {

        int [] arr = {10, 3, 20, 40, 2};

        int res = nobleInteger(arr);

        if (res != -1)

            System.out.println("The noble "

                     + "integer is "+ res);

        else

            System.out.println("No Noble "

                        + "Integer Found");

    }

}

python3

# Python3 программа для поиска Noble
# элементов в массиве.

  
# Возвращает Благородное целое число, если
# присутствует, иначе возвращает -1.

def nobleInteger(arr, size):

  

    for i in range(0, size):

      

        count = 0

        for j in range(0, size):

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

                count += 1

        # Если счет больше

        количество элементов равно

        # до обр [я]

        if (count == arr[i]):

            return arr[i]

      

    return -1

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

arr = [10, 3, 20, 40, 2]

size = len(arr)

res = nobleInteger(arr,size)

if (res != -1): 

    print("The noble integer is ",

                              res)

else:

    print("No Noble Integer Found")

  
# Этот код предоставлен
# Смита.

C #

// C # программа для поиска благородных элементов
// в массиве.

using System;

  

class GFG {

      

    // Возвращает Благородное целое число, если присутствует,

    // иначе возвращает -1.

    public static int nobleInteger(int [] arr)

    {

        int size = arr.Length;

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

        {

            int count = 0;

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

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

                    count++;

  

            // Если количество больших элементов

            // равно arr [i]

            if (count == arr[i])

                return arr[i];

        }

          

        return -1;

    }

  

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

    public static void Main()

    {

        int [] arr = {10, 3, 20, 40, 2};

        int res = nobleInteger(arr);

        if (res != -1)

            Console.Write("The noble integer"

                              + " is "+ res);

        else

            Console.Write("No Noble Integer"

                                 + " Found");

    }

}

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

PHP

<?php
// PHP программа для поиска Noble
// элементы в массиве.

  
// Возвращает Благородное целое число
// если присутствует, иначе возвращает -1.

function nobleInteger( $arr, $size)

{

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

    {

        $count = 0;

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

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

                $count++;

                  

        // Если количество больших элементов

        // равно arr [i]

        if ($count == $arr[$i])

            return $arr[$i];

    }

      

    return -1;

}

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

$arr = array(10, 3, 20, 40, 2);

$size = count($arr);

$res = nobleInteger($arr, $size);

  

if ($res != -1)

    echo "The noble integer is ", $res;

else

    echo "No Noble Integer Found";

  
// Этот код предоставлен anuj_67 ..
?>


Выход :

The noble integer is 3

Способ 2 (использовать сортировку)

  1. Сортируйте массив Arr [] в порядке возрастания. Этот шаг занимает (O (nlogn)).
  2. Итерация по массиву. Сравните значение индекса i с количеством элементов после индекса i. Если arr [i] равно числу элементов после arr [i], это благородное целое число. Условие для проверки: (A [i] == length-i-1). Этот шаг занимает O (n).

Примечание . Массив может содержать повторяющиеся элементы. Таким образом, мы должны пропустить элементы (смежные элементы в отсортированном массиве), которые являются одинаковыми.

C ++

// C ++ программа для поиска благородных элементов
// в массиве.
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает Благородное целое число, если присутствует,
// иначе возвращает -1.

int nobleInteger(int arr[], int n)

{

    sort(arr, arr + n);

  

    // Возвращаем элемент Noble, если он есть

    // позапрошлый.

    for (int i = 0; i < n - 1; i++)

    {

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

            continue;

  

        // В случае дубликатов мы

        // достигнуть последнего вхождения здесь.

        if (arr[i] == n - i - 1)

            return arr[i];

    }

    if (arr[n - 1] == 0)

        return arr[n - 1];

    return -1;

}

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

int main()

{

    int arr[] = {10, 3, 20, 40, 2};

    int res = nobleInteger(arr, 5);

    if (res != -1)

        cout << "The noble integer is " << res;

    else

        cout << "No Noble Integer Found";

    return 0;

}

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

Джава

// Java программа для поиска благородных элементов
// в массиве.

import java.util.Arrays;

  

public class Main

{

    // Возвращает Благородное целое число, если присутствует,

    // иначе возвращает -1.

    public static int nobleInteger(int arr[])

    {

        Arrays.sort(arr);

  

        // Возвращаем элемент Noble, если он есть

        // позапрошлый.

        int n = arr.length;

        for (int i=0; i<n-1; i++)

        {

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

                continue;

  

            // В случае дубликатов мы

            // достигнуть последнего вхождения здесь.

            if (arr[i] == n-i-1)

                return arr[i];

        }

  

        if (arr[n-1] == 0)

            return arr[n-1];

  

        return -1;

    }

  

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

    public static void main(String args[])

    {

        int [] arr = {10, 3, 20, 40, 2};

        int res = nobleInteger(arr);

        if (res != -1)

            System.out.println("The noble integer is "+ res);

        else

            System.out.println("No Noble Integer Found");

    }

}

питон

# Python3 код для поиска благородных элементов
# в массиве

  

def nobleInteger(arr):

      

    arr.sort()

      

    # Вернуть элемент Noble, если

    # присутствует до последнего

    n = len(arr)

      

    for i in range(n - 1):

          

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

            continue

              

        # В случае дубликатов мы достигаем

        # последний случай здесь

        if arr[i] == n - i - 1:

            return arr[i]

      

    if arr[n - 1] == 0:

        return arr[n - 1]

    return -1

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

arr = [10, 3, 20, 40, 2]

  

res = nobleInteger(arr)

  

if res != -1:

    print("The noble integer is", res)

else:

    print("No Noble Intger Found")

  
# Этот код добавлен
# Мохит Кумар

C #

// C # программа для поиска благородных элементов
// в массиве.

using System;

  

public class GFG {

      

    public static int nobleInteger(int[] arr)

    {

        Array.Sort(arr);

  

        // Возвращаем элемент Noble, если он есть

        // позапрошлый.

        int n = arr.Length;

        for (int i = 0; i < n-1; i++)

        {

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

                continue;

  

            // В случае дубликатов мы

            // достигнуть последнего вхождения здесь.

            if (arr[i] == n-i-1)

                return arr[i];

        }

  

        if (arr[n-1] == 0)

            return arr[n-1];

  

        return -1;

    }

      

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

    static public void Main ()

    {

        int [] arr = {10, 3, 20, 40, 2};

        int res = nobleInteger(arr);

        if (res != -1)

        Console.Write("The noble integer is "

                                      + res);

        else

            Console.Write("No Noble Integer " 

                                  + "Found");

          

    }

}

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

PHP

<?php
// PHP программа для поиска благородных элементов

  
// Возвращает Благородное целое число, если присутствует,
// иначе возвращает -1.

function nobleInteger( $arr)

    {

        sort($arr);

  

        // Возвращаем элемент Noble, если

        // присутствует до последнего

        $n = count($arr);

        for ( $i = 0; $i < $n - 1; $i++)

        {

            if ($arr[$i] == $arr[$i + 1])

                continue;

  

            // В случае дубликатов мы

            // достигнуть последнего вхождения здесь.

            if ($arr[$i] == $n - $i - 1)

                return $arr[$i];

        }

  

        if ($arr[$n - 1] == 0)

            return $arr[$n - 1];

  

        return -1;

    }

  

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

    $arr = array(10, 3, 20, 40, 2);

    $res = nobleInteger($arr);

    if ($res != -1)

        echo "The noble integer is ", $res;

    else

        echo "No Noble Integer Found";

  
// Этот код предоставлен anuj_67.
?>


Выход :

The noble integer is 3.

Эта статья предоставлена Saloni Baweja . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Благородные целые числа в массиве (количество больших элементов равно значению)

0.00 (0%) 0 votes