सबै तत्वहरू सँगै k भन्दा कम वा बराबर ल्याउन न्यूनतम स्वैपहरू आवश्यक हुन्छ


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन AppDynamics तथ्य फोरकाइट्स माइक्रोसफ्ट
एरे

समस्या "न्यूनतम स्वैपहरू आवश्यक हुन्छ सबै k तत्वहरू भन्दा कम वा बराबर सँगै ल्याउनको लागि" बताउँछ कि तपाईंसँग पूर्णांक हुन्छ array। समस्या कथनले swaps को सानो स count्ख्या पत्ता लगाउन को लागी सोध्छ जुन तत्वहरू सँगै प्राप्त गर्न आवश्यक हुन्छ जुन दिईएको संख्या k भन्दा कम वा बराबर हो।

उदाहरणका

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

स्पष्टीकरण

केवल १ स्वाप आवश्यक छ। 1 लाई २ सँग बदल्न सकिन्छ ताकि,, २, १, र together सँगै आउँदछ।

अल्गोरिदम

  1. सबै एलिमेन्ट्स का गणना प्राप्त गर्नुहोस् जुन के बराबर भन्दा कम छ।
  2. सबै एलिमेन्ट्स काउन्ट पाउनुहोस् जुन k भन्दा ठूलो छ।
  3. सानोको मानमा आउटपुट सेट गर्नुहोस्।
  4. I = 0 र j = गणना बाट एर्रे ट्रान्सवर्स गर्नुहोस्।
    1. यदि एर्रे [i] k को मान भन्दा ठूलो छ जाँच गर्नुहोस्, तब, १ द्वारा सानोको मान घटाउनुहोस्।
    2. यदि एर्रे [j] k को मान भन्दा ठूलो छ जाँच गर्नुहोस्, तब, १ द्वारा सानोको मान बढाउनुहोस्।
    3. न्यूनतम आउटपुट र सानो बीच फेला पार्नुहोस् र आउटपुटमा भण्डार गर्नुहोस्।
  5. आउटपुटको मान फिर्ता गर्नुहोस्।

स्पष्टीकरण

हामीले एउटा दिएका छौं array of पूर्णांकहरूर k नामक इन्टिजर मान, हामीले पत्ता लगाउन लगायौं कि कतिवटा न्यूनतम स्वपहरू के-के भन्दा कम वा बराबर सबै तत्वहरू सँगै ल्याउन आवश्यक छ। याद गर्नुहोस् हामीले केवल न्यूनतम स्वपहरू मात्र खोज्नु पर्छ।

यसको लागि, हामी एलिमेन्ट्सको संख्या गणना गर्न गइरहेछौं जुन k भन्दा कम वा बराबर हुन्छ, र यसलाई सानो भ्यारीएबलमा भण्डार गर्छौं। त्यसो भए सानो भ्यारीएबलले सानो संख्याको गणनालाई समात्छ जुन के के भन्दा कम वा बराबर हुन्छ। त्यो गणनाको समान, हामी सबै नम्बरहरू गणना गर्दछौं जुन संख्या k भन्दा ठूलो छ। आउटपुटको मानलाई सानोमा सेट गर्नुहोस्, पछि, हामी यस आउटपुटसँग मानहरू तुलना गर्नेछौं र यसै साथ भण्डार गरिरहनेछौं। यदि हामीले उदाहरण लिनुभयो जुन माथिको उल्लेख छ, smaller सानोको गणना हो, र १ ठूलो गणना गर्दछ।

I = 0, j = सानो लिनुहोस्, एर्रे जाँच गर्नुहोस् [i] र एर [j] k को मान भन्दा ठूलो छ, यदि arr [i] ठूलो छ भने, array सानो बनाउनुहोस् यदि [j] ठूलो छ भने सानोको गणना बढाउनुहोस्।

एकै साथ हामी आउटपुट र सानो संख्याको बीचको न्यूनतम पत्ता लगाउनेछौं, हामी लुपमा हामी ट्र्यावर्सिंग गर्दैछौं हामी दुबै अपरेसन गरिरहेछौं, सानोको मान घटाउन र सानोको मान बढाउन। अन्त्यमा, हामीले भर्खरै आउटपुटको मान फिर्ता गर्नुपर्नेछ। किनभने यो चाहिएको आउटपुट हुनेछ।

सबै तत्वहरू सँगै k भन्दा कम वा बराबर ल्याउन न्यूनतम स्वैपहरू आवश्यक हुन्छ

कोड

C ++ कोड कम से कम वा बराबर k सँगै ल्याउन सबै तत्वहरू ल्याउन आवश्यक न्यूनतम स्वैपहरू फेला पार्न

#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

जाभा कोड न्यूनतम स्वैपहरू फेला पार्न आवश्यक हुन्छ सबै k तत्वहरू भन्दा कम वा बराबर सँगै ल्याउनका लागि

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

जटिलता विश्लेषण

समय जटिलता

ऊ) जहाँ "n " एर्रेमा एलिमेन्ट्सको संख्या हो। किनभने हामीसँग लूपहरू थिए जसमा नेस्टेड लूपहरू थिएनन्। यस प्रकार समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (१) कुनै अतिरिक्त ठाउँको आवश्यक छ। त्यसैले ठाउँ जटिलता स्थिर छ।