K-ээс бага эсвэл тэнцүү бүх элементүүдийг нэгтгэхэд шаардагдах хамгийн бага солилцоо  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны AppDynamics програм Мэдээллийн багц Фуркайт Microsoft-
Array

"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 = count-ээс хөндлөн гаргана.
    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-ээс бага эсвэл тэнцүү бүх элементүүдийг нэгтгэхэд шаардагдах хамгийн бага солилцооPin

код  

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) хаана "н ” нь массив дахь элементүүдийн тоо юм. Учир нь бид үүрэндээ гогцоогүй гогцоотой байсан. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь шугаман юм.

мөн үзнэ үү
Массив дахь давтагдаагүй элементүүдийн (ялгаатай) нийлбэрийг ол

Сансрын нарийн төвөгтэй байдал

O (1) нэмэлт зай шаардагдахгүй тул. Тиймээс сансрын нарийн төвөгтэй байдал тогтмол байдаг.