सर्व घटक एकत्र आणण्यासाठी किमान स्वॅप आवश्यक आहेत


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन अ‍ॅपडायनामिक्स फॅक्टसेट फोरकाइट्स मायक्रोसॉफ्ट
अरे

“के घटकांपेक्षा कमी किंवा समान सर्व घटक आणण्यासाठी आवश्यक किमान स्वॅप्स” ही समस्या सांगते की आपल्याकडे पूर्णांक आहे अॅरे. प्रॉब्लेम स्टेटमेंटमध्ये दिलेली संख्या के पेक्षा कमी किंवा त्या समान असलेल्या घटकांना एकत्रित करण्यासाठी स्वॅप्सची सर्वात लहान मोजणी शोधण्यास सांगितले जाते.

उदाहरण

arr[]={4,6,1,3,2}, k = 4
1

स्पष्टीकरण

फक्त 1 स्वॅप आवश्यक आहे. 6 2 सह अदलाबदल करता येईल जेणेकरून 4, 2, 1 आणि 3 एकत्र येतील.

अल्गोरिदम

  1. के समानतेपेक्षा कमी असलेल्या सर्व घटकांची गणना मिळवा.
  2. के पेक्षा मोठे असलेल्या सर्व घटकांची गणना मिळवा.
  3. लहान च्या व्हॅल्यू वर आउटपुट सेट करा.
  4. I = 0 आणि j = गणना वरून अ‍ॅरेला जा.
    1. अ‍ॅरे [i] के च्या मूल्यापेक्षा मोठे असल्याचे तपासा, तर लहानचे मूल्य १ ने कमी करा.
    2. अ‍ॅरे [j] के च्या मूल्यापेक्षा मोठे असल्याचे तपासा, तर लहानचे मूल्य १ ने वाढवा.
    3. आउटपुट आणि छोट्यामधील किमान शोधा आणि आउटपुटमध्ये ठेवा.
  5. आउटपुटचे मूल्य परत करा.

स्पष्टीकरण

आम्ही एक दिले आहे अॅरे of पूर्णांकआणि के नावाचे पूर्णांक मूल्य, आम्ही के पेक्षा कमी किंवा त्या समान असलेल्या सर्व घटकांना एकत्रित करण्यासाठी किती किमान स्वॅप आवश्यक आहेत हे शोधण्यास सांगितले. लक्षात ठेवा आम्हाला फक्त किमान स्वॅप्स शोधणे आवश्यक आहे.

त्यासाठी आपण के च्या तुलनेत कमी किंवा त्या समान घटकांची संख्या मोजू आणि त्यास लहान व्हेरिएबलमधे संचित करू. तर लहान व्हेरिएबल लहान संख्येची संख्या धारण करेल जे के पेक्षा कमी किंवा त्या समान असतील. त्या संख्येप्रमाणेच, आम्ही के-के संख्येपेक्षा जास्त असलेल्या सर्व संख्या मोजू. आउटपुटचे व्हॅल्यू छोट्या वर सेट करा, नंतर आपण या आउटपुटसह व्हॅल्यूजची तुलना करू आणि त्यामध्ये एकाच वेळी स्टोअर करत राहू. जर आपण वर नमूद केलेले उदाहरण घेतले तर 4 ही लहान ची गणना आहे आणि 1 ही सर्वात मोठी गणना आहे.

I = 0, j = छोटा, अ‍ॅरे तपासा [i] आणि अ‍ॅर [j] k च्या व्हॅल्यूपेक्षा जास्त असल्यास अ‍ॅरे [i] जास्त असल्यास अ‍ॅरे [j] कमी असल्यास छोटीची संख्या कमी करा. त्यापेक्षा लहान म्हणजे लहानची संख्या वाढवा.

त्याच बरोबर आउटपुट आणि छोट्या संख्येमधील किमान शोधू, ज्या लूपमध्ये आपण ट्रॅव्हर्स करत आहोत त्या दोन्ही ऑपरेशन्स करत आहोत, लहानचे मूल्य कमी करण्यासाठी आणि लहानचे मूल्य वाढवण्यासाठी. शेवटी आपल्याला आउटपुटचे मूल्य परत करावे लागेल. कारण त्यात इच्छित आउटपुट असेल.

सर्व घटक एकत्र आणण्यासाठी किमान स्वॅप आवश्यक आहेत

कोड

सर्व घटक एकत्र आणण्यासाठी आवश्यक असलेल्या किमान स्वॅप्स शोधण्यासाठी सी ++ कोड

#include <iostream>

using namespace std;

int minimumSwapToK(int arr[], int n, int k)
{
    int count = 0;
    for (int i = 0; i < n; ++i)
        if (arr[i] <= k)
            ++count;

    int bad = 0;
    for (int i = 0; i < count; ++i)
        if (arr[i] > k)
            ++bad;

    int ans = bad;
    for (int i = 0, j = count; j < n; ++i, ++j)
    {

        if (arr[i] > k)
            --bad;

        if (arr[j] > k)
            ++bad;

        ans = min(ans, bad);
    }
    return ans;
}

int main()
{
    int arr[] = {4,6,1,3,2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
    int result = minimumSwapToK(arr, n, k);
    cout <<result;
    return 0;
}
1

सर्व घटक एकत्र आणण्यासाठी आवश्यक असलेल्या कमीतकमी स्वॅप्स शोधण्यासाठी जावा कोड

class minimumSwaps
{
    public static int minimumSwapToK(int arr[], int n, int k)
    {

        int count = 0;
        for (int i = 0; i < n; ++i)
            if (arr[i] <= k)
                ++count;

        int bad = 0;
        for (int i = 0; i < count; ++i)
            if (arr[i] > k)
                ++bad;

        int ans = bad;
        for (int i = 0, j = count; j < n; ++i, ++j)
        {

            if (arr[i] > k)
                --bad;

            if (arr[j] > k)
                ++bad;

            ans = Math.min(ans, bad);
        }
        return ans;
    }
    public static void main(String[] args)
    {
        int arr[] = {4,6,1,3,2};
        int n = arr.length;
        int k = 4;
        int result = minimumSwapToK(arr, n, k);
        System.out.println(result);

    }
}
1

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे "n” अ‍ॅरे मधील घटकांची संख्या. कारण आमच्याकडे रन लूप होते ज्यात नेस्टेड लूप नसतात. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

ओ (1) अतिरिक्त जागेची आवश्यकता नसल्यामुळे. तर जागेची जटिलता स्थिर आहे.