Рубрики

Максимальное значение K такое, что массив имеет по крайней мере K элементов, которые> = K

Учитывая массив положительных целых чисел, найдите максимально возможное значение K, так что массив имеет по крайней мере K элементов, которые больше или равны K. Массив не отсортирован и может содержать повторяющиеся значения.

Примеры :

Input: [2, 3, 4, 5, 6, 7]
Output: 4
Explanation : 4 elements [4, 5, 6, 7] 
            are greater than equal to 4

Input: [1, 2, 3, 4]
Output: 2
Explanation : 3 elements [2, 3, 4] are 
               greater than equal to 2

Input: [4, 7, 2, 3, 8]
Output: 3 
Explanation : 4 elements [4, 7, 3, 8] 
          are greater than equal to 3
 

Input: [6, 7, 9, 8, 10]
Output: 5
Explanation : All 5 elements are greater
              than equal to 5 

Ожидаемая сложность времени: O (n)

Метод 1 [Простой: O (n 2 ) время]
Пусть размер входного массива будет n. Давайте рассмотрим следующие важные наблюдения.

  1. Максимально возможное значение результата может быть n. Мы получаем максимально возможное значение, когда все элементы больше или равны n. Например, если входной массив равен {10, 20, 30}, n равен 3. Значение результата не может быть больше 3.
  2. Минимально возможное значение было бы 1. Примерный случай, когда получить этот вывод, когда все элементы равны 1.

Таким образом, мы можем запустить цикл от n до 1 и посчитать больше элементов для каждого значения.

C ++

// C ++ программа для поиска максимально возможного значения K
// такой, что массив имеет как минимум K элементов, которые
// больше или равно K.
#include <iostream>

using namespace std;

  
// Функция для возврата максимально возможного значения K
// такой, что массив имеет как минимум K элементов, которые
// больше или равно K

int findMaximumNum(unsigned int arr[], int n)

{

    // вывод может содержать любое число от n до 0

    // где n - длина массива

  

    // Мы начинаем цикл с n, так как нам нужно найти

    // максимально возможное значение

    for (int i = n; i >= 1; i--)

    {

        // count содержит общее количество элементов

        // во входном массиве, который больше чем равен i

        int count = 0;

  

        // переходим во входной массив и находим количество

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

            if (i <= arr[j])

                count++;

  

        if (count >= i)

          return i;

    }    

    return 1;

}

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

int main()

{

    unsigned int arr[] = {1, 2, 3, 8, 10 };

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

    cout << findMaximumNum(arr, n);

    return 0;

}

Джава

// Java программа для поиска максимума
// возможное значение K такое, что
// массив содержит не менее K элементов
// которые больше или равны K.

import java.io.*;

  

class GFG 

{

  
// Функция для возврата максимума
// возможное значение K такое, что
// массив имеет как минимум K элементов
// больше или равно K

static int findMaximumNum(int arr[], 

                          int n)

{

    // вывод может содержать любой

    // число от n до 0 где

    // n - длина массива

  

    // Запускаем цикл из n

    // как нам нужно найти

    // максимально возможное значение

    for (int i = n; i >= 1; i--)

    {

        // count содержит всего

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

        // во входном массиве

        // больше чем я

        int count = 0;

  

        // пройти через вход

        // массив и найти количество

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

            if (i <= arr[j])

                count++;

  

        if (count >= i)

        return i;

    

    return 1;

}

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

public static void main (String[] args) 

{

int arr[] = {1, 2, 3, 8, 10 };

int n = arr.length; 

System.out.println(findMaximumNum(arr, n));
}
}

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

python3

# python 3 программа для поиска максимально возможного значения K
# такой, что массив имеет как минимум K элементов, которые
# больше или равно K.

  
# Функция для возврата максимально возможного значения K
# такой, что массив имеет как минимум K элементов, которые
# больше или равно K

def findMaximumNum(arr, n):

    # output может содержать любое число от n до 0

    # где n - длина массива

  

    # Запускаем цикл из n, так как нам нужно найти

    # максимально возможное значение

    i = n

    while(i >= 1):

        # count содержит общее количество элементов

        # во входном массиве, которые больше, чем я

        count = 0

  

        # пройти входной массив и найти количество

        for j in range(0,n,1):

            if (i <= arr[j]):

                count += 1

  

        if (count >= i):

            return i

              

        i -= 1

      

    return 1

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

if __name__ == '__main__':

    arr = [1, 2, 3, 8, 10]

    n = len(arr)

    print(findMaximumNum(arr, n))

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

C #

// C # программа для поиска максимума
// возможное значение K такое, что
// массив содержит не менее K элементов
// которые больше или равны K.

using System;

  

class GFG

{

      
// Функция для возврата максимума
// возможное значение K такое, что
// массив имеет как минимум K элементов
// больше или равно K

static int findMaximumNum(int []arr, 

                          int n)

{

    // вывод может содержать любой

    // число от n до 0 где

    // n - длина массива

  

    // Запускаем цикл из n

    // как нам нужно найти

    // максимально возможное значение

    for (int i = n; i >= 1; i--)

    {

        // count содержит всего

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

        // во входном массиве

        // больше чем я

        int count = 0;

  

        // пройти через вход

        // массив и найти количество

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

            if (i <= arr[j])

                count++;

  

        if (count >= i)

        return i;

    

    return 1;

}

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

static public void Main ()

{

    int []arr = {1, 2, 3, 8, 10 };

    int n = arr.Length; 

    Console.WriteLine(findMaximumNum(arr, n));

}
}

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

PHP

<?php
// PHP программа для поиска максимума
// возможное значение K такое, что
// массив содержит не менее K элементов
// больше или
// равно К.

  
// Функция для возврата максимума
// возможное значение K такое, что
// массив имеет как минимум K элементов
// больше или
// равно K

function findMaximumNum($arr, $n)

{

    // вывод может содержать любой

    // число от n до 0 где

    // n - длина массива

  

    // Мы начинаем цикл с

    // n как нам нужно найти

    // максимально возможное значение

    for ($i = $n; $i >= 1; $i--)

    {

        // count содержит всего

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

        // входной массив, который

        // больше чем я

        $count = 0;

  

        // пройти через вход

        // массив и найти количество

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

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

                $count++;

  

        if ($count >= $i)

        return $i;

    

    return 1;

}

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

$arr = array (1, 2, 3, 8, 10);

$n = sizeof($arr);

echo findMaximumNum($arr, $n);

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


Выход :

3

Метод 2 [Эффективный: O (n) время и O (n) дополнительное пространство]
1) Идея состоит в том, чтобы построить аксиллярный массив размером n + 1 и использовать этот массив, чтобы найти количество больших элементов во входном массиве. Пусть вспомогательный массив будет freq []. Мы инициализируем все элементы этого массива как 0.

2) Обрабатываем все входные элементы.
а) Если элемент arr [i] меньше n, то мы увеличиваем его частоту, т. е. делаем freq [arr [i]] ++.
б) Иначе мы увеличиваем freq [n].

3) После шага 2 у нас есть две вещи.
a) Частоты элементов для элементов, меньших, чем n, хранятся в freq [0..n-1].
б) Количество элементов больше, чем n, хранящихся в freq [n].

Наконец, мы обрабатываем массив freq [] в обратном направлении, чтобы найти выходные данные, сохраняя сумму обработанных значений.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска максимально возможного значения K, такого
// этот массив имеет по крайней мере K элементов, которые больше
// чем или равно К.
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата максимально возможного значения K, такого
// этот массив имеет как минимум K элементов, которые больше
// чем или равно К.

int findMaximumNum(unsigned int arr[], int n)

{

    // строим подмышечный массив размером n + 1 и

    // инициализируем массив с 0

    vector<int> freq(n+1, 0);

  

    // храним частоту элементов

    // входной массив в подмышечном массиве

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

    {

        // Если элемент меньше n, обновить его

        // частота

        if (arr[i] < n)

            freq[arr[i]]++;

  

        // Иначе счетчик приращений элементов больше

        // чем п.

        else

            freq[n]++;

    }

  

    // сумма хранит количество элементов во входном массиве

    // больше или равно текущему

    // показатель

    int sum = 0;

  

    // сканируем вспомогательный массив в обратном направлении

    for (int i = n; i > 0; i--)

    {

        sum += freq[i];

  

        // если сумма больше текущего индекса,

        // текущий индекс - это ответ

        if (sum >= i)

            return i;

    }

}

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

int main()

{

    unsigned int arr[] = {1, 2, 3, 8, 10 };

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

  

    cout << findMaximumNum(arr, n);

  

    return 0;

}

Джава

// Java программа для поиска максимально возможного значения K, такого
// этот массив имеет по крайней мере K элементов, которые больше
// чем или равно К.

  

import java.util.Vector;

  

class GFG {

  
// Функция для возврата максимально возможного значения K, такого
// этот массив имеет как минимум K элементов, которые больше
// чем или равно К.

    static int findMaximumNum(int arr[], int n) {

        // строим подмышечный массив размером n + 1 и

        // инициализируем массив с 0

        Vector<Integer> freq = new Vector<>();

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

            freq.add(i, 0);

        }

  

        // храним частоту элементов

        // входной массив в подмышечном массиве

        for (int i = 0; i < n; i++) {

            // Если элемент меньше n, обновить его

            // частота

            if (arr[i] < n) // частота [обр [я]] ++;

            {

                freq.add(arr[i], freq.get(arr[i]) + 1);

            } // Иначе счетчик приращений элементов больше

            // чем п.

            else {

                freq.add(n, freq.get(n) + 1);

            }

            // частота [п] ++;

        }

  

        // сумма хранит количество элементов во входном массиве

        // больше или равно текущему

        // показатель

        int sum = 0;

  

        // сканируем вспомогательный массив в обратном направлении

        for (int i = n; i > 0; i--) {

            sum += freq.get(i);

  

            // если сумма больше текущего индекса,

            // текущий индекс - это ответ

            if (sum >= i) {

                return i;

            }

        }

        return 0;

    }

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

    public static void main(String[] args) {

        int arr[] = {1, 2, 3, 8, 10};

        int n = arr.length;

        System.out.println(findMaximumNum(arr, n));

    }

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

C #

// C # программа для поиска максимально возможного значения K, такого
// этот массив имеет по крайней мере K элементов, которые больше
// чем или равно К.

using System;

using System.Collections.Generic;

  

class GFG

  

    // Функция для возврата максимально возможного значения K, такого

    // этот массив имеет как минимум K элементов, которые больше

    // чем или равно К.

    static int findMaximumNum(int []arr, int n) 

    

        // строим подмышечный массив размером n + 1 и

        // инициализируем массив с 0

        List<int> freq = new List<int>(); 

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

        

            freq.Insert(i, 0); 

        

  

        // храним частоту элементов

        // входной массив в подмышечном массиве

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

        

            // Если элемент меньше n, обновить его

            // частота

            if (arr[i] < n) // частота [обр [я]] ++;

            

                freq.Insert(arr[i], freq[arr[i]] + 1); 

            

            // Иначе счетчик приращений элементов больше

            // чем п.

            else 

            

                freq.Insert(n, freq[n] + 1); 

            

            // частота [п] ++;

        

  

        // сумма хранит количество элементов во входном массиве

        // больше или равно текущему

        // показатель

        int sum = 0; 

  

        // сканируем вспомогательный массив в обратном направлении

        for (int i = n; i > 0; i--) 

        

            sum += freq[i]; 

  

            // если сумма больше текущего индекса,

            // текущий индекс - это ответ

            if (sum >= i) 

            

                return i; 

            

        

        return 0; 

    

  

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

    public static void Main() 

    

        int []arr = {1, 2, 3, 8, 10}; 

        int n = arr.Length; 

        Console.WriteLine(findMaximumNum(arr, n)); 

    

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

Выход :

3

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

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

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

Максимальное значение K такое, что массив имеет по крайней мере K элементов, которые> = K

0.00 (0%) 0 votes