K- ից պակաս կամ հավասար բոլոր տարրերը միավորելու համար անհրաժեշտ նվազագույն փոխանակումներ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon AppDynamics Փաստեր Ֆուրկիտներ Microsoft
Դասավորություն

«K- ից պակաս կամ հավասար բոլոր տարրերը միավորելու համար անհրաժեշտ նվազագույն փոխանակումներ» խնդիրը նշում է, որ դուք ունեք ամբողջ թիվ դասավորություն, Խնդրի հայտարարությունը խնդրում է պարզել swap- ի ամենափոքր քանակը, որը կպահանջվի տրված 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 = փոքր վերցնելով, ստուգեք array [i] և ar [j] ավելի մեծ է, քան k արժեքը, եթե ar [i] ավելի մեծ է, ապա նվազեցրեք ավելի փոքր, եթե զանգվածը [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

Java- ի կոդը `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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ "n » զանգվածում տարրերի քանակն է: Քանի որ մենք գործարկել էինք օղակներ, որոնք չունեին տեղադրված օղակներ: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

Ո (1) քանի որ լրացուցիչ տարածք չի պահանջվում: Այսպիսով, տիեզերական բարդությունը կայուն է: