ټولې جوړې (a ، b) په یو صف کې ومومئ چې٪ b = k


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon ارسیم د فراه تاريخي کلا لارښود وړیا چارج د ياهو
پیشه هاش ماډول ریاضي

ستونزه بیان

ستونزه "یو جوړه کې ټولې جوړې (a ، b) ومومئ لکه٪ b = k" په ګوته کوي چې تاسو ته د یو بشپړ صف او دقیق ارزښت په نامه درکول کیږي. k. د ستونزې بیان غوښتنه کوي چې جوړه په داسې ډول ومومي چې په صف کې x٪ y = k (ورکړل شوی ارزښت).

بېلګه

arr[] = {3, 4, 7, 5, 6 }
k = 3
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

تشریح

دا 4 جوړې تایید شوي کله چې٪ b = k ریښتیا وي.

ټولې جوړې (a ، b) په یو صف کې ومومئ چې٪ b = k

arr[]={2, 3, 5, 1},
k = 2
(2, 3) (2, 5) (5, 3)

تشریح

دا 3 جوړې تایید شوي کله چې٪ b = k ریښتیا وي.

الګوریتم

  1. اعلامیه a نقشه او د هغې یو دلیل د a په څیر وټاکئ بولین.
  2. اصل وټاکئ سور او د صفونو ټول ارزښتونه په نقشه کې د ریښتیني بولین ارزښت سره زیرمه کړئ.
  3. د بولین کوم بدیل وټاکئ جوړه جوړه غلط ته.
  4. د صف له 0 څخه تر n-1 پورې وغځیږئ (د صف د اوږدوالی دی).
    1. وګوره چې ورکړل شوی K ارزښت په نقشه کې ننوتلی دی او هم k د اوسني سر عنصر څخه کوچنی دی. که ریښتیا وي ، نو بیا ارزښت k چاپ کړئ او هم هغه صف عنصر او د بولین ارزښت ریښتیني کړئ.
    2. وګوره که k د اوسني سرکي عنصر څخه کم یا مساوي وي.
      1. که ریښتیا وي نو بیا یې ویکټور رامینځته کړئ او د آر آر [i] - ک ارزښت ټول تقسیم کونکي ومومئ او دا یې په ویکتور کې ذخیره کړئ.
      2. هغه ویکتور تعقیب کړئ او وګورئ چې ایا د ویکتور او سرې عنصر هغه عنصر جوړه ده چې کوم حالت پوره کوي کله چې ماډولو ترسره کیږي.
        1. د ویکتور او اوسني سري عنصر چاپ کړئ او د بولین ارزښت ریښتیني کړئ.
  5. بیرته راګرځی جوړه جوړه.

تشریح

د عدد یو صف او یو عدد ارزښت k ورکړل شو. جوړه په داسې ډول ومومئ کله چې موږ په جوړه (x ، y) لکه ماډلولو عملیات ترسره کوو لکه x٪ y = k ، نو بیا موږ اړتیا لرو چې جوړه جوړه کړو ، موږ باید دا د بشپړ انټیر صف سره ترسره کړو. ټولې هغه جوړه ومومئ کوم چې k k ورکوي کله چې موږ په x y y شمیره کې ماډولو عملیات ترسره کړو. د دې لپاره ، موږ د کلکسیون یا STL څخه کار واخلو چې ویلټر او نقشه نومیږي.

ټولې د صف عناصر په نقشه کې واچوئ او دا ټول د "ریښتیني" بولین ارزښت سره نښه کړئ. موږ اړتیا لرو د بولین متغیر پیل کړو جوړه جوړه غلط ته. موږ دا تازه کوو کله چې موږ سم جوړه وموندل شي. بیا موږ به اوس له صف څخه تیر شو. او وګورئ چې ورکړل شوي k ارزښت په نقشه کې شتون لري که نه. همدارنګه که k د اوسني سرکي عنصر څخه کم وي. بیا موږ دا جوړه چاپ کړه. ځکه چې کله موږ کوچنۍ شمیره په لوی شمیر سره وویشو نو دا به پاتې شمیره د کوچني شمیر په توګه پریږدي.

که پورته حالت غلط شي ، نو بیا موږ ګورو چې اوسني عنصر له k څخه لوی دی. که ریښتیا وي ، نو بیا موږ اړتیا لرو چې یو ویکتور اعلان کړو چیرې چې موږ د اوسني سرکي عنصر او k توپیر تیروو ، کوم چې به دا ویکتور بیرته راشي چې په هغه کې جوړه جوړه ممکن ارزښتونه بیرته راشي. موږ هر یو ارزښت غوره کوو او دا به وګورو چې آیا په ویکٹر کې د اوسني عنصر موډولیو بیرته راوړل شوي ارزښت پاتې k چمتو کوي یا نه. که دا ریښتیا وي نو جوړه جوړه کړئ او د جوڑیچیک ارزښت ریښتیا په نښه کړئ ، پدې معنی چې موږ لږترلږه یوه جوړه وموندله. د ورته مرحلو سره نور ارزښت سره پرمختګ وکړئ او ټولې احتمالي پایلې چاپ کړئ.

کوډ

په A+ کې د ټولې جوړې (a ، b) موندلو لپاره C ++ کې تطبیق لکه دا چې٪ b = k

#include <unordered_map>
#include<vector>
#include<iostream>
#include<math.h>

using namespace std;

vector<int> findPossibleDiv(int n)
{
    vector<int> vecDiv;

    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            if (n / i == i)
                vecDiv.push_back(i);
            else
            {
                vecDiv.push_back(i);
                vecDiv.push_back(n / i);
            }
        }
    }
    return vecDiv;
}
bool pairModulousK(int arr[], int n, int k)
{
    unordered_map<int, bool> MAP;
    for (int i = 0; i < n; i++)
        MAP[arr[i]] = true;

    bool pairCheck = false;
    for (int i = 0; i < n; i++)
    {
        if (MAP[k] && k < arr[i])
        {
            cout << "(" << k << ", " << arr[i] << ") ";
            pairCheck = true;
        }
        if (arr[i] >= k)
        {
            vector<int> vec = findPossibleDiv(arr[i] - k);

            for (int j = 0; j < vec.size(); j++)
            {
                if (arr[i] % vec[j] == k && arr[i] != vec[j] && MAP[vec[j]])
                {
                    cout << "(" << arr[i] << ", "<< vec[j] << ") ";
                    pairCheck = true;
                }
            }
            vec.clear();
        }
    }
    return pairCheck;
}
int main()
{
    int arr[] = { 3, 4, 7, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    if (pairModulousK(arr, n, k) == false)
        cout << "No such pair exists";
    return 0;
}
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

د جاوا کوډ چې په یوه قطار کې ټولې جوړې (a ، b) ومومي داسې چې٪ b = k

import java.util.HashMap;
import java.util.Vector;

class PairModuloK
{
    public static Vector<Integer> findPossibleDiv(int n)
    {
        Vector<Integer> vecDiv = new Vector<>();

        for (int i = 1; i <= Math.sqrt(n); i++)
        {
            if (n % i == 0)
            {
                if (n / i == i)
                    vecDiv.add(i);
                else
                {
                    vecDiv.add(i);
                    vecDiv.add(n / i);
                }
            }
        }
        return vecDiv;
    }
    public static boolean pairModulousK(int arr[], int n, int k)
    {
        HashMap<Integer, Boolean> MAP = new HashMap<>();
        for (int i = 0; i < n; i++)
            MAP.put(arr[i], true);

        boolean pairCheck = false;
        for (int i = 0; i < n; i++)
        {
            if (MAP.get(k) && k < arr[i])
            {
                System.out.print("(" + k + ", " + arr[i] + ") ");
                pairCheck = true;
            }
            if (arr[i] >= k)
            {
                Vector<Integer> vec = findPossibleDiv(arr[i] - k);

                for (int j = 0; j < vec.size(); j++)
                {
                    if (arr[i] % vec.get(j) == k && arr[i] != vec.get(j) && MAP.get(vec.get(j)))
                    {
                        System.out.print("(" + arr[i] + ", "
                                         + vec.get(j) + ") ");
                        pairCheck = true;
                    }
                }
                vec.clear();
            }
        }

        return pairCheck;
    }
    public static void main(String args[])
    {
        int arr[] = {3, 4, 7, 6, 5};
        int k = 3;

        if (pairModulousK(arr, arr.length, k) == false)
            System.out.println("No such pair exists");
    }
}
(3, 4) (3, 7) (7, 4) (3, 6) (3, 5)

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n * sqrt (اعظمي)) هلته "اعظمي" په صف کې اعظمي عنصر دی. دا وخت پیچلتیا ترلاسه شوه ځکه چې موږ کارول

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. دا ځای په نقشه کې د عناصرو خوندي کولو لپاره اړین دی.