Бардык элементтерди kден аз же ага тең келтирүү үчүн минималдуу своптор


Кыйынчылык деңгээли жеңил
Көп суралган Amazon AppDynamics Factset Fourkites Microsoft
согуштук тизме

"K элементтеринен аз же ага тең болгон бардык элементтерди бириктирүү үчүн талап кылынган минималдуу своптор" маселеси сизде бүтүн сан бар экендигин билдирет согуштук тизме. Маселенин коюлушу, берилген k санынан кичине же ага барабар болгон элементтерди бириктирүү үчүн талап кылынган своптордун эң кичине санын табууну сурайт.

мисал

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

түшүндүрүү

1 гана алмашуу талап кылынат. 6, 2, 4 жана 2 биригиши үчүн, 1 менен 3ди алмаштырса болот.

Algorithm

  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 + дан кичине же ага барабар элементтерди бириктирүү үчүн минималдуу свопторду табуу үчүн 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 элементтеринен кем же барабар болгон элементтерди бириктирүү үчүн талап кылынган минималдуу свопторду табуу үчүн Java коду

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 ” массивдеги элементтердин саны. Себеби бизде уя салынбаган циклдер болгон. Ошентип, убакыттын татаалдыгы сызыктуу.

Космостун татаалдыгы

O (1) ашыкча орун талап кылынбагандыктан. Демек, космостун татаалдыгы туруктуу.