அனைத்து உறுப்புகளையும் k ஐ விட குறைவாகவோ அல்லது சமமாகவோ கொண்டுவர குறைந்தபட்ச பரிமாற்றங்கள் தேவை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப் டைனமிக்ஸ் உண்மை ஃபோர்கைட்டுகள் மைக்ரோசாப்ட்
அணி

“எல்லா உறுப்புகளையும் k ஐ விடக் குறைவாகவோ அல்லது சமமாகவோ கொண்டுவருவதற்குத் தேவையான குறைந்தபட்ச இடமாற்றங்கள்” என்ற சிக்கல் உங்களிடம் ஒரு முழு எண் இருப்பதாகக் கூறுகிறது வரிசை. கொடுக்கப்பட்ட எண் k ஐ விட குறைவாகவோ அல்லது சமமாகவோ இருக்கும் உறுப்புகளை ஒன்றிணைக்க தேவைப்படும் சிறிய அளவிலான இடமாற்றுகளை கண்டுபிடிக்க சிக்கல் அறிக்கை கேட்கிறது.

உதாரணமாக

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

விளக்கம்

1 இடமாற்று மட்டுமே தேவை. 6 ஐ 2 உடன் மாற்றலாம், இதனால் 4, 2, 1 மற்றும் 3 ஒன்றாக வரும்.

அல்காரிதம்

  1. K க்கு சமமான அனைத்து உறுப்புகளின் எண்ணிக்கையைப் பெறுங்கள்.
  2. K ஐ விட அதிகமான அனைத்து உறுப்புகளின் எண்ணிக்கையைப் பெறுங்கள்.
  3. வெளியீட்டை சிறிய மதிப்புக்கு அமைக்கவும்.
  4. I = 0 மற்றும் j = எண்ணிக்கையிலிருந்து வரிசையை கடந்து செல்லுங்கள்.
    1. வரிசை [i] k இன் மதிப்பை விட அதிகமாக இருக்கிறதா என்று சரிபார்க்கவும், பின்னர், சிறிய மதிப்பை 1 ஆகக் குறைக்கவும்.
    2. வரிசை [j] k இன் மதிப்பை விட அதிகமாக இருக்கிறதா என்று சரிபார்க்கவும், பின்னர், சிறிய மதிப்பை 1 ஆல் அதிகரிக்கவும்.
    3. வெளியீட்டிற்கும் சிறியவற்றுக்கும் இடையிலான குறைந்தபட்சத்தைக் கண்டுபிடித்து வெளியீட்டில் சேமிக்கவும்.
  5. வெளியீட்டின் மதிப்பைத் தரவும்.

விளக்கம்

நாங்கள் ஒரு கொடுத்துள்ளோம் வரிசை of முழு, மற்றும் k எனப்படும் ஒரு முழு எண் மதிப்பு, k ஐ விடக் குறைவாகவோ அல்லது சமமாகவோ இருக்கும் அனைத்து உறுப்புகளையும் ஒன்றாகப் பெற எத்தனை குறைந்தபட்ச இடமாற்றுகள் தேவை என்பதைக் கேட்கிறோம். குறைந்தபட்ச இடமாற்றுகளை மட்டுமே நாம் கண்டுபிடிக்க வேண்டும் என்பதை நினைவில் கொள்க.

அதற்காக, k ஐ விடக் குறைவாகவோ அல்லது சமமாகவோ இருக்கும் உறுப்புகளின் எண்ணிக்கையை எண்ணி, அதை சிறிய மாறியில் சேமிக்கப் போகிறோம். எனவே சிறிய மாறி k ஐ விட குறைவாகவோ அல்லது சமமாகவோ இருக்கும் சிறிய எண்ணிக்கையின் எண்ணிக்கையை வைத்திருக்கும். அந்த எண்ணிக்கையைப் போலவே, k எண்ணை விட அதிகமான அனைத்து எண்களையும் எண்ணுகிறோம். வெளியீட்டின் மதிப்பை சிறியதாக அமைக்கவும், பின்னர், இந்த வெளியீட்டோடு மதிப்புகளை ஒப்பிட்டு, ஒரே நேரத்தில் சேமித்து வைப்போம். மேலே குறிப்பிடப்பட்ட ஒரு உதாரணத்தை நாம் எடுத்துக் கொண்டால், 4 என்பது சிறிய எண்ணிக்கையாகும், மேலும் 1 என்பது பெரிய எண்ணிக்கையாகும்.

I = 0, j = சிறியது, வரிசையை சரிபார்க்கவும் [i] மற்றும் arr [j] k இன் மதிப்பை விட பெரியது, arr [i] அதிகமாக இருந்தால், வரிசை [j] என்றால் சிறிய எண்ணிக்கையை குறைக்கவும். பெரியது பின்னர் சிறிய எண்ணிக்கையை அதிகரிக்கும்.

அதேசமயம், வெளியீட்டிற்கும் சிறிய எண்ணிற்கும் இடையிலான குறைந்தபட்சத்தைக் கண்டுபிடிப்போம், சுழற்சியில் நாம் பயணிக்கிறோம், நாங்கள் இரண்டு செயல்பாடுகளையும் செய்கிறோம், சிறிய மதிப்பைக் குறைக்கவும், சிறிய மதிப்பை அதிகரிக்கவும். கடைசியாக, வெளியீட்டின் மதிப்பை நாம் திருப்பித் தர வேண்டும். ஏனெனில் அது விரும்பிய வெளியீட்டைக் கொண்டிருக்கும்.

அனைத்து உறுப்புகளையும் k ஐ விட குறைவாகவோ அல்லது சமமாகவோ கொண்டுவர குறைந்தபட்ச பரிமாற்றங்கள் தேவை

குறியீடு

அனைத்து உறுப்புகளையும் 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) எங்கே "n ” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. ஏனென்றால், உள்ளமைந்த சுழல்கள் இல்லாத சுழல்களை நாங்கள் இயக்கினோம். இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (1) கூடுதல் இடம் தேவையில்லை என்பதால். எனவே விண்வெளி சிக்கலானது நிலையானது.