Рубрики

Подсчет пар в массиве, которые содержат i * arr [i]> j * arr [j]

Учитывая массив целых чисел arr [0..n-1], подсчитайте все пары (arr [i], arr [j]) в таком, что i * arr [i]> j * arr [j], 0 = < я <J <N.

Примеры :

Input : arr[] = {5 , 0, 10, 2, 4, 1, 6}
Output: 5
 Pairs which hold condition i*arr[i] > j*arr[j]
 are (10, 2) (10, 4) (10, 1) (2, 1) (4, 1)

Input  : arr[] = {8, 4, 2, 1}
Output : 2

Простое решение — запустить два цикла. Выберите каждый элемент массива один за другим, и для каждого элемента найдите элемент в правой части массива, который содержит условие, затем увеличьте счетчик и значение последнего возвращаемого счетчика.
Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для подсчета всех пар, которые
// держим условие i * arr [i]> j * arr [j]
#include<iostream>

using namespace std;

  
// Возвращаем количество пар в указанном массиве
// такой, что i * arr [i]> j * arr [j]

int CountPair(int arr[] , int n )

{

    int result = 0; // Инициализировать результат

  

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

    {

        // Генерируем всю пару и увеличиваем

        // счетчик, если удерживать заданное условие

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

            if (i*arr[i] > j*arr[j] )

                result ++;

    }

    return result;

}

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

int main()

{

    int arr[] = {5 , 0, 10, 2, 4, 1, 6} ;

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

    cout << "Count of Pairs : "

         << CountPair(arr, n);

    return 0;

}

Джава

// Java-код для подсчета пар в
// массив, содержащий i * arr [i]> j * arr [j]

class GFG {

      

    // Возвращаем количество пар в указанном массиве

    // такой, что i * arr [i]> j * arr [j]

    public static int CountPair(int arr[] , int n )

    {

        int result = 0; // Инициализировать результат

       

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

        {

            // Генерируем всю пару и увеличиваем

            // счетчик, если удерживать заданное условие

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

                if (i*arr[i] > j*arr[j] )

                    result ++;

        }

        return result;

    }

      

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

    public static void main(String[] args) 

    {

        int arr[] = {5 , 0, 10, 2, 4, 1, 6} ;

        int n = arr.length;

        System.out.println("Count of Pairs : " +

                            CountPair(arr, n));

    }

  }

// Этот код предоставлен Арнавом Кр. Мандал.

python3

# C # Код для подсчета пар в
# массив, содержащий i * arr [i]> j * arr [j]

  
# Возвращаем количество пар в указанном массиве
# такой, что i * arr [i]> j * arr [j]

def CountPair(arr , n ):

      

    # Инициализировать результат

    result = 0;

      

    for i in range (0, n):

          

        # Генерация всех пар и приращений

        # счетчик, если удерживать заданное условие

        j = i + 1

        while(j < n):

            if (i * arr[i] > j * arr[j] ):

                result = result +1

            j = j + 1

    return result;

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

      

arr = [5, 0, 10, 2, 4, 1, 6]

n = len(arr)

print("Count of Pairs : " , CountPair(arr, n))

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

C #

// C # код для подсчета пар в
// массив, содержащий i * arr [i]> j * arr [j]

using System;

  

class GFG

{

    // Возвращаем количество пар в указанном массиве

    // такой, что i * arr [i]> j * arr [j]

    public static int CountPair(int []arr , int n )

    {

        // Инициализировать результат

        int result = 0;

      

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

        {

            // Генерируем всю пару и увеличиваем

            // счетчик, если удерживать заданное условие

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

                if (i*arr[i] > j*arr[j] )

                    result ++;

        }

        return result;

    }

      

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

    public static void Main() 

    {

        int []arr = {5, 0, 10, 2, 4, 1, 6};

        int n = arr.Length;

        Console.WriteLine("Count of Pairs : " +

                           CountPair(arr, n));

    }

}

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

PHP

<?php
// PHP-программа для подсчета всех пар
// держим условие i * arr [i]> j * arr [j]

  
// Возвращаем количество пар в указанном массиве
// такой, что i * arr [i]> j * arr [j]

function CountPair($arr , $n )

{

      

    // Инициализировать результат

    $result = 0; 

      

  

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

    {

          

        // Генерируем всю пару и увеличиваем

        // счетчик, если удерживать заданное условие

        for ($j = $i + 1; $j < $n; $j++)

            if ($i $arr[$i] > $j * $arr[$j] )

                $result ++;

    }

    return $result;

}

  

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

    $arr = array(5, 0, 10, 2, 4, 1, 6) ;

    $n = sizeof($arr);

    echo "Count of Pairs : ",

    CountPair($arr, $n);

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


Выход:

Count of Pairs : 5

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

Эффективное решение этой проблемы занимает O (n log n) времени. Идея основана на интересном факте об этой проблеме, заключающейся в том, что после изменения массива таким образом, что каждый элемент умножается на его индекс, эта проблема преобразуется в число инверсий в массиве .
Алгоритм:

Given an array 'arr' and it's size 'n'
1) First traversal array element, i goes from 0 to n-1
   a) Multiple each element with its index arr[i] = arr[i] * i 
2) After that step 1. whole process is similar to Count Inversions in an array. 

Ниже реализация идеи выше

C ++

// C ++ программа для подсчета всех пар, которые
// держим условие i * arr [i]> j * arr [j]
#include <bits/stdc++.h>

using namespace std;

  
/ * Эта функция объединяет два отсортированных массива и

   возвращает счетчик инверсий в массивах. * /

int merge(int arr[], int temp[], int left,

                       int mid, int right)

{

    int inv_count = 0;

  

    int i = left; / * индекс для левого подмассива * /

    int j = mid;  / * индекс для правого подмассива * /

    int k = left; / * ndex для результирующего подмассива * /

    while ((i <= mid - 1) && (j <= right))

    {

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

            temp[k++] = arr[i++];

        else

        {

            temp[k++] = arr[j++];

  

            inv_count = inv_count + (mid - i);

        }

    }

  

    / * Копировать оставшиеся элементы слева

     subarray (если есть) для temp * /

    while (i <= mid - 1)

        temp[k++] = arr[i++];

  

    / * Копировать остальные элементы права

     subarray (если есть) для temp * /

    while (j <= right)

        temp[k++] = arr[j++];

  

    / * Копировать обратно объединенные элементы в оригинал

      массив * /

    for (i=left; i <= right; i++)

        arr[i] = temp[i];

  

    return inv_count;

}

  
/ * Вспомогательная рекурсивная функция, которая сортирует

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

   инверсии в массиве. * /

int _mergeSort(int arr[], int temp[], int left,

                                      int right)

{

    int mid, inv_count = 0;

    if (right > left)

    {

        / * Разделите массив на две части и вызовите

          _mergeSortAndCountInv () для каждого из

          части */

        mid = (right + left)/2;

  

        / * Счетчик инверсий будет суммой инверсий в

           левая часть, правая часть и количество инверсий

           в слиянии * /

        inv_count  = _mergeSort(arr, temp, left, mid);

        inv_count += _mergeSort(arr, temp, mid+1, right);

  

        / * Объединить две части * /

        inv_count += merge(arr, temp, left, mid+1, right);

    }

  

    return inv_count;

}

  
/ * Эта функция сортирует входной массив и

   возвращает количество инверсий в

   массив * /

int countPairs(int arr[], int n)

{

    // Модифицируем массив так, чтобы проблема сводилась к

    // считать проблему инверсии.

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

        arr[i] = i*arr[i];

  

    // Считаем инверсии, используя ту же логику, что и

    // ниже сообщения

    // https://www.geeksforgeeks.org/counting-inversions/amp/

    int temp[n];

    return _mergeSort(arr, temp, 0, n - 1);

}

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

int main()

{

    int arr[] = {5, 0, 10, 2, 4, 1, 6};

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

    cout << "Count of Pairs : "

         << countPairs(arr, n);

    return 0;

}

Джава

// Java-программа для подсчета всех пар
// держим условие i * arr [i]> j * arr [j]

import java.io.*;

  

class GFG 

{

    // Эта функция объединяет два отсортированных массива и

    // возвращает количество инверсий в массивах.

    static int merge(int arr[], int temp[], int left,

                                   int mid, int right)

    {

        int inv_count = 0;

          

        / * индекс для левого подмассива * / 

        int i = left; 

          

        / * индекс для правого подмассива * /

        int j = mid; 

        / * ndex для результирующего подмассива * /

        int k = left; 

          

        while ((i <= mid - 1) && (j <= right))

        {

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

                temp[k++] = arr[i++];

            else

            {

                temp[k++] = arr[j++];

      

                inv_count = inv_count + (mid - i);

            }

        }

      

        / * Копировать оставшиеся элементы слева

        subarray (если есть) для temp * /

        while (i <= mid - 1)

            temp[k++] = arr[i++];

      

        / * Копировать остальные элементы права

        subarray (если есть) для temp * /

        while (j <= right)

            temp[k++] = arr[j++];

      

        // Копируем обратно объединенные элементы

        // в исходный массив

        for (i = left; i <= right; i++)

            arr[i] = temp[i];

      

        return inv_count;

    }

      

    / * Вспомогательная рекурсивная функция

    который сортирует входной массив и

    возвращает количество инверсий

    в массиве. * /

    static int _mergeSort(int arr[], int temp[], 

                               int left,int right)

    {

        int mid, inv_count = 0;

        if (right > left)

        {

            / * Разделите массив на две части и вызовите

            _mergeSortAndCountInv () для каждого из

            части */

            mid = (right + left) / 2;

      

            // Счетчик инверсий будет суммой инверсий в

            // левая часть, правая часть и количество инверсий

            // в слиянии

            inv_count = _mergeSort(arr, temp, left, mid);

            inv_count += _mergeSort(arr, temp, mid+1, right);

      

            / * Объединить две части * /

            inv_count += merge(arr, temp, left, mid+1, right);

        }

      

        return inv_count;

    }

      

    // Эта функция сортирует входной массив и

    // возвращает количество инверсий в

    // массив

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

    {

        // Модифицируем массив так, чтобы проблема сводилась к

        // считать проблему инверсии.

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

            arr[i] = i * arr[i];

      

        // Считаем инверсии, используя ту же логику, что и

        // ниже сообщения

        // https://www.geeksforgeeks.org/counting-inversions/amp/

        int temp[] = new int [n];

        return _mergeSort(arr, temp, 0, n - 1);

    }

      

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

  

    public static void main (String[] args) 

    {

        int arr[] = {5, 0, 10, 2, 4, 1, 6};

        int n = arr.length;

        System.out.print( "Count of Pairs : "

                          + countPairs(arr, n));  

          

    }

}

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

Python 3

# Python 3 программа для подсчета всех
# пара, которая содержит условие
# i * arr [i]> j * arr [j]

  
# Эта функция объединяет два
# отсортированные массивы и возвраты
Количество инверсий в массивах.

def merge(arr, temp, left, mid, right):

  

    inv_count = 0

  

    i = left # индекс для левого подмассива

    j = mid # индекс для правого подмассива

    k = left # ndex для результирующего подмассива

    while ((i <= mid - 1) and (j <= right)):

      

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

            temp[k] = arr[i]

            i += 1

            k += 1

        else:

          

            temp[k] = arr[j]

            k += 1

            j += 1

  

            inv_count = inv_count + (mid - i)

  

    # Скопируйте оставшиеся элементы слева

    # subarray (если есть) для temp

    while (i <= mid - 1):

        temp[k] = arr[i]

        i += 1

        k += 1

  

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

    # subarray (если есть) для temp

    while (j <= right):

        temp[k] = arr[j]

        k += 1

        j += 1

  

    # Скопировать обратно объединенные элементы

    # к исходному массиву

    for i in range(left, right + 1):

        arr[i] = temp[i]

  

    return inv_count

  
# Вспомогательная рекурсивная функция
# сортирует входной массив и
# возвращает количество инверсий
# в массиве.

def _mergeSort(arr, temp, left, right):

  

    inv_count = 0

    if (right > left):

      

        # Разделить массив на две части

        # и вызвать _mergeSortAndCountInv ()

        # для каждой из частей

        mid = (right + left) // 2

  

        # Счетчик инверсии будет суммой

        # инверсии в левой части, правой части x

        # и количество инверсий в слиянии

        inv_count = _mergeSort(arr, temp, left, mid)

        inv_count += _mergeSort(arr, temp, 

                                mid + 1, right)

  

        # Объединить две части

        inv_count += merge(arr, temp, left,     

                           mid + 1, right)

  

    return inv_count

  
# Эта функция сортирует ввод
# массив и возвращает число
Количество инверсий в массиве

def countPairs(arr, n):

      

    # Изменить массив так, чтобы проблема

    # уменьшает, чтобы считать проблему инверсии.

    for i in range(n):

        arr[i] = i * arr[i]

  

    # Считать инверсии, используя тот же

    # логика, как показано ниже

    # https://www.geeksforgeeks.org/counting-inversions/amp/

    temp = [0] * n

    return _mergeSort(arr, temp, 0, n - 1)

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

if __name__ == "__main__":

    arr = [5, 0, 10, 2, 4, 1, 6]

    n = len(arr)

    print("Count of Pairs : "

           countPairs(arr, n))

             
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для подсчета всех пар
// держим условие i * arr [i]> j * arr [j]

using System;

  

class GFG 

{

    // Эта функция объединяет два отсортированных массива и

    // возвращает количество инверсий в массивах.

    static int merge(int []arr, int []temp, int left,

                                int mid, int right)

    {

        int inv_count = 0;

          

        / * индекс для левого подмассива * /

        int i = left; 

          

        / * индекс для правого подмассива * /

        int j = mid; 

        / * ndex для результирующего подмассива * /

        int k = left; 

          

        while ((i <= mid - 1) && (j <= right))

        {

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

                temp[k++] = arr[i++];

            else

            {

                temp[k++] = arr[j++];

      

                inv_count = inv_count + (mid - i);

            }

        }

      

        / * Копировать оставшиеся элементы слева

        subarray (если есть) для temp * /

        while (i <= mid - 1)

            temp[k++] = arr[i++];

      

        / * Копировать остальные элементы права

        subarray (если есть) для temp * /

        while (j <= right)

            temp[k++] = arr[j++];

      

        // Копируем обратно объединенные элементы

        // в исходный массив

        for (i = left; i <= right; i++)

            arr[i] = temp[i];

      

        return inv_count;

    }

      

    / * Вспомогательная рекурсивная функция

    который сортирует входной массив и

    возвращает количество инверсий

    в массиве. * /

    static int _mergeSort(int []arr, int []temp, 

                            int left,int right)

    {

        int mid, inv_count = 0;

        if (right > left)

        {

            / * Разделите массив на две части и вызовите

            _mergeSortAndCountInv () для каждого из

            части */

            mid = (right + left) / 2;

      

            // Счетчик инверсий будет суммой инверсий в

            // левая часть, правая часть и количество инверсий

            // в слиянии

            inv_count = _mergeSort(arr, temp, left, mid);

            inv_count += _mergeSort(arr, temp, mid+1, right);

      

            / * Объединить две части * /

            inv_count += merge(arr, temp, left, mid+1, right);

        }

      

        return inv_count;

    }

      

    // Эта функция сортирует входной массив и

    // возвращает количество инверсий в

    // массив

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

    {

        // Модифицируем массив так, чтобы проблема сводилась к

        // считать проблему инверсии.

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

            arr[i] = i * arr[i];

      

        // Считаем инверсии, используя ту же логику, что и

        // ниже сообщения

        // https://www.geeksforgeeks.org/counting-inversions/amp/

        int []temp = new int [n];

        return _mergeSort(arr, temp, 0, n - 1);

    }

      

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

  

    public static void Main () 

    {

        int []arr = {5, 0, 10, 2, 4, 1, 6};

        int n = arr.Length;

        Console.WriteLine( "Count of Pairs : "

                        + countPairs(arr, n)); 

          

    }

}

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


Выход:

Count of Pairs : 5

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

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

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

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

Подсчет пар в массиве, которые содержат i * arr [i]> j * arr [j]

0.00 (0%) 0 votes