ሁሉንም ንጥረ ነገሮች ከ k በታች ወይም እኩል በአንድ ላይ ለማምጣት የሚያስፈልጉ አነስተኛ ስዋፕዎች


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን AppDynamics ፋርስት አራት ኪይትስ የ Microsoft
ሰልፍ

ችግሩ “ከካ 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 ያነሰ ወይም እኩል የሆኑ አነስተኛ ቁጥሮችን ይይዛል ፡፡ ከዛ ቆጠራ ጋር በሚመሳሰል መልኩ ከቁጥር የሚበልጡትን ሁሉንም ቁጥሮች እንቆጥራለን ፡፡ የውጤት እሴቱን ወደ ትንሽ ያቀናብሩ ፣ በኋላ ላይ እሴቶቹን ከዚህ ውፅዓት ጋር በማወዳደር እና በተመሳሳይ ጊዜ ማከማቸቱን እንቀጥላለን። ከላይ የተጠቀሰውን አንድ ምሳሌ ከወሰድን 4 የቁጥር አነስተኛ ሲሆን 1 ደግሞ የከፍተኛ ቁጥር ነው።

I = 0 ፣ j = አነስን በመያዝ ድርድሩን ያቋርጡ ፣ የቼክ ድርድር [i] እና arr [j] ከ k እሴት ይበልጣል ፣ arr [i] ከዚያ የበለጠ ከሆነ ፣ ድርድር ቢኖር አነስተኛውን ቁጥር ይቀንሱ ይበልጣል ከዚያም የአናሳውን ቁጥር ይጨምሩ።

በተመሳሳይ ጊዜ በውጤቱ እና በትንሽ ቁጥሩ መካከል ያለውን አነስተኛውን እናገኛለን ፣ በምናቋርጠው ዑደት ውስጥ ሁለቱን ክንውኖች እናከናውናለን ፣ አነስተኛውን እሴት ለመቀነስ እና የአነስተኛ እሴት ለመጨመር ፡፡ በመጨረሻ የውጤት ዋጋን መመለስ ብቻ አለብን ፡፡ ምክንያቱም የሚፈለገውን ውጤት ሊኖረው ይችላል ፡፡

ሁሉንም ንጥረ ነገሮች ከ k በታች ወይም እኩል በአንድ ላይ ለማምጣት የሚያስፈልጉ አነስተኛ ስዋፕዎች

ኮድ

ሁሉንም ንጥረ ነገሮች ከ k በታች ወይም እኩል ለማምጣት የሚያስፈልጉ አነስተኛ ስዋፕ ለማግኘት የ C ++ ኮድ

#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) ተጨማሪ ቦታ ስለማያስፈልግ ፡፡ ስለዚህ የቦታ ውስብስብነት ቋሚ ነው።