Рубрики

Найти количество элементов больше чем k в отсортированном массиве

Учитывая отсортированный массив arr [] целых чисел и целое число k , задача состоит в том, чтобы найти количество элементов в массиве, которые больше k . Обратите внимание, что k может присутствовать или не присутствовать в массиве.

Примеры:

Input: arr[] = {2, 3, 5, 6, 6, 9}, k = 6
Output: 1

Input: arr[] = {1, 1, 2, 5, 5, 7}, k = 8
Output: 0

Подход: Идея состоит в том, чтобы выполнить бинарный поиск и найти число элементов, превышающее k.

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

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

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

int countGreater(int arr[], int n, int k)

{

    int l = 0;

    int r = n - 1;

  

    // Сохраняет индекс самого левого элемента

    // из массива, который больше k

    int leftGreater = n;

  

    // Находит количество элементов больше k

    while (l <= r) {

        int m = l + (r - l) / 2;

  

        // Если средний элемент больше чем

        // k обновляем leftGreater и r

        if (arr[m] > k) {

            leftGreater = m;

            r = m - 1;

        }

  

        // Если средний элемент меньше

        // или равно k update l

        else

            l = m + 1;

    }

  

    // Возвращаем количество элементов больше k

    return (n - leftGreater);

}

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

int main()

{

    int arr[] = { 3, 3, 4, 7, 7, 7, 11, 13, 13 };

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

  

    int k = 7;

  

    cout << countGreater(arr, n, k);

  

    return 0;

}

Джава

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

class GFG

{

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

static int countGreater(int arr[], int n, int k)

{

    int l = 0;

    int r = n - 1;

  

    // Сохраняет индекс самого левого элемента

    // из массива, который больше k

    int leftGreater = n;

  

    // Находит количество элементов больше k

    while (l <= r) {

        int m = l + (r - l) / 2;

  

        // Если средний элемент больше чем

        // k обновляем leftGreater и r

        if (arr[m] > k) {

            leftGreater = m;

            r = m - 1;

        }

  

        // Если средний элемент меньше

        // или равно k update l

        else

            l = m + 1;

    }

  

    // Возвращаем количество элементов больше k

    return (n - leftGreater);

}

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

public static void main(String[] args)

{

    int arr[] = { 3, 3, 4, 7, 7, 7, 11, 13, 13 };

    int n = arr.length;

  

    int k = 7;

  

    System.out.println(countGreater(arr, n, k));

}
}

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

python3

# Python 3 реализация подхода

  
# Функция для возврата количества элементов
# из массива, превышающего k

def countGreater(arr, n, k):

    l = 0

    r = n - 1

  

    # Хранит индекс самого левого элемента

    # из массива, который больше чем k

    leftGreater = n

  

    # Находит количество элементов больше чем k

    while (l <= r):

        m = int(l + (r - l) / 2)

  

        # Если средний элемент больше чем

        # k обновить leftGreater и r

        if (arr[m] > k):

            leftGreater = m

            r = m - 1

  

        # Если средний элемент меньше

        # или равно к обновлению л

        else:

            l = m + 1

  

    # Вернуть количество элементов

    # больше чем k

    return (n - leftGreater)

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

if __name__ == '__main__':

    arr = [3, 3, 4, 7, 7, 7, 11, 13, 13]

    n = len(arr)

    k = 7

  

    print(countGreater(arr, n, k))

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

C #

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

using System;

  

class GFG

{

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

static int countGreater(int[]arr, int n, int k)

{

    int l = 0;

    int r = n - 1;

  

    // Сохраняет индекс самого левого элемента

    // из массива, который больше k

    int leftGreater = n;

  

    // Находит количество элементов больше k

    while (l <= r) 

    {

        int m = l + (r - l) / 2;

  

        // Если средний элемент больше чем

        // k обновляем leftGreater и r

        if (arr[m] > k) 

        {

            leftGreater = m;

            r = m - 1;

        }

  

        // Если средний элемент меньше

        // или равно k update l

        else

            l = m + 1;

    }

  

    // Возвращаем количество элементов больше k

    return (n - leftGreater);

}

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

public static void Main()

{

    int[] arr = { 3, 3, 4, 7, 7, 7, 11, 13, 13 };

    int n = arr.Length;

  

    int k = 7;

  

    Console.WriteLine(countGreater(arr, n, k));

}
}

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

PHP

<?php
// PHP реализация подхода

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

function countGreater($arr, $n, $k)

{

    $l = 0;

    $r = $n - 1;

  

    // Сохраняет индекс самого левого элемента

    // из массива, который больше k

    $leftGreater = $n;

  

    // Находит количество элементов больше k

    while ($l <= $r

    {

        $m = $l + (int)(($r - $l) / 2);

  

        // Если средний элемент больше чем

        // k обновляем leftGreater и r

        if ($arr[$m] > $k

        {

            $leftGreater = $m;

            $r = $m - 1;

        }

  

        // Если средний элемент меньше

        // или равно k update l

        else

            $l = $m + 1;

    }

  

    // Возвращаем количество элементов больше k

    return ($n - $leftGreater);

}

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

$arr = array(3, 3, 4, 7, 7, 7, 11, 13, 13);

$n = sizeof($arr);

$k = 7;

  

echo countGreater($arr, $n, $k);

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

Выход:

3

Сложность времени: O (log (n)), где n — количество элементов в массиве.

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

Найти количество элементов больше чем k в отсортированном массиве

0.00 (0%) 0 votes