جفت ها را از دو آرایه مرتب شده که مجموع آنها برابر با مقدار داده شده x بشمارید  


سطح دشواری ساده
اغلب در بانک بازار سیسکو دژ شرکت Honeywell PayU Roblox Taxi4Sure Yandex
صف مخلوط مرتب سازی STL

بیان مسأله  

"جفتها را از دو بشمار مرتب شده اند آرایه هایی که مجموع آنها برابر با مقدار x مشخص است ”بیان می کند که به شما دو آرایه مرتب شده از اعداد صحیح و یک مقدار صحیح به نام sum داده می شود. بیانیه مسئله می خواهد تعداد کل جفت را که در یک مقدار معین جمع می کند پیدا کند.

مثال  

arr1[] = {1, 6, 8, 11}

arr2[] = {1, 3, 5, 9}

sum = 9
2

 

توضیح: زیرا در یک آرایه معین مجموعاً 2 جفت وجود دارد که (6 ، 3) و (8 ، 1) است. زیرا جفت های دیگر مجموع یا بیشتر یا کمتر از جمع مورد نیاز دارند.

arr1[] = {3, 5, 11, 14};

arr2[] = {2, 4, 5, 11}

sum = 16
3

 

توضیح: زیرا در مجموع 3 جفت در آرایه داده شده وجود دارد که (5 ، 11) ، (11 ، 5) و (14 ، 2) است.

الگوریتم برای شمارش جفت از دو آرایه مرتب شده که مجموع آنها برابر با یک مقدار داده شده x باشد  

1. Set count and left to 0, and right to n-1 where n is the length of the array.
2. While left is less than m and right is greater than equal to 0, repeat the following the steps-
    1. If the sum of arr[left] and arr[right] is equal to the given value, then increase the value of count and left by 1 and decrease the value of right by 1.
    2. Else check if the addition of arr[left] and arr[right] is less than the given value sum, then increase the value of left by 1.
    3. Decrease the value of right by 1 if the addition is greater than the sum.
3. Return the count value after traversing the arrays.

توضیح

به شما دو عدد صحیح مرتب شده داده شده است آرایه ها و یک مقدار صحیح به نام sum. و از ما خواسته شده است تا دریابیم که چند جفت احتمالی را می توان تشکیل داد که در یک مقدار معین جمع می شود. بنابراین ، ما می خواهیم از تکنیکی مشابه به عنوان روش جستجوی دودویی استفاده کنیم. این نیز دلیل این است که ما مقادیر ورودی را با افزایش ترتیب در نظر می گیریم. به این ترتیب ، ما می توانیم از آن تکنیک در حل این سوال استفاده کنیم. در غیر اینصورت ما آرایه را مرتب می کردیم.

همچنین مشاهده کنید
راه حل کد Leetcode سیستم پارکینگ را طراحی کنید

ما می خواهیم مقدار را تعیین کنیم تعداد دفعات مشاهده به 0. زیرا اگر مقدار جفت مورد نیاز را پیدا کنیم ، مقدار آن را 1 افزایش خواهیم داد. یک جفت از دو مقدار تشکیل خواهد شد. البته ، ما می خواهیم بررسی کنیم که آیا جمع آن مقدار در یک جفت برابر است با مقدار مقدار داده شده. اگر درست باشد مقدار شمارش را 1 افزایش خواهیم داد حلقه در حالی که به این روش سپس تا جایی که مقادیر m (m طول یکی از آرایه ها باشد) و r (جایی که r یک برابر کمتر از طول آرایه است) و r بزرگتر از 0 می شود.

در یک حلقه ، بررسی خواهیم کرد که آیا مقدار جفت به مقدار داده شده اضافه می شود یا خیر. سپس ، هر زمان که این شرایط درست شد ، یک جفت پیدا کردیم. اگر جمع کمتر از مقدار داده شده باشد ، حلقه را ادامه خواهیم داد. سپس مقدار را افزایش خواهیم داد l توسط 1 دیگر ما فقط مقدار را کاهش می دهیم r در 1. در پایان ، مقدار شمارش را برمی گردانیم.

جفت ها را از دو آرایه مرتب شده که مجموع آنها برابر با مقدار داده شده x بشماریدسنجاق

رمز  

کد C ++ برای شمارش جفتهایی که حاصل جمع آنها x از دو آرایه مرتب شده است

#include<iostream>

using namespace std;

int getPairofsum(int arr1[], int arr2[], int m, int n, int sum)
{
    int count = 0;
    int left = 0, right = n - 1;

    while (left < m && right >= 0)
    {
        if ((arr1[left] + arr2[right]) == sum)
        {
            left++;
            right--;
            count++;
        }
        else if ((arr1[left] + arr2[right]) < sum)
            left++;
        else
            right--;
    }
    return count;
}
int main()
{
    int arr1[] = {1, 6, 8, 11};
    int arr2[] = {1, 3, 5, 9};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    int sum = 9;
    cout << "Count = "<< getPairofsum(arr1, arr2, m, n, sum);
    return 0;
}
Count = 2

 

همچنین مشاهده کنید
محدوده سeriesالات بدون به روزرسانی

کد جاوا برای شمردن جفتهایی که مجموع آنها x از دو آرایه مرتب شده است

class PairofSum
{
    public static int getPairofsum(int arr1[],int arr2[], int m, int n, int sum)
    {
        int count = 0;
        int left = 0, right = n - 1;

        while (left < m && right >= 0)
        {
            if ((arr1[left] + arr2[right]) == sum)
            {
                left++;
                right--;
                count++;
            }
            else if ((arr1[left] + arr2[right]) < sum)
                left++;
            else
                right--;
        }
        return count;
    }
    public static void main (String[] args)
    {
        int arr1[] = {1, 6, 8, 11};
        int arr2[] = {1, 3, 5, 9};
        int m = arr1.length;
        int n = arr2.length;
        int sum = 9;
        System.out.println( "Count = "+ getPairofsum(arr1, arr2, m, n, sum));
    }
}
Count = 2

 

تحلیل پیچیدگی  

پیچیدگی زمان

O (m + n) جایی که "متر" و "n" تعداد عناصر arr1 و arr2 است. زیرا حداکثر ما می توانیم سفر کنیم m + n است.

پیچیدگی فضا

O (1) زیرا فضای اضافی مورد نیاز نیست. بنابراین یک پیچیدگی فضا ثابت حاصل می شود.