ការផ្លាស់ប្តូរអប្បបរមាដែលត្រូវការដើម្បីនាំយកធាតុទាំងអស់តិចជាងឬស្មើ k ជាមួយគ្នា


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon AppDynamics រោងចក្រ Fourkites ក្រុមហ៊ុន Microsoft
អារេ

បញ្ហា“ ការផ្លាស់ប្តូរអប្បបរមាតម្រូវឱ្យមានធាតុទាំងអស់តិចជាងឬស្មើ k ជាមួយគ្នា” បញ្ជាក់ថាអ្នកមានចំនួនគត់ អារេ។ សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យរកការរាប់តូចបំផុតនៃការប្តូរដែលនឹងត្រូវបានទាមទារដើម្បីទទួលបានធាតុជាមួយគ្នាដែលតូចជាងឬស្មើនឹងលេខដែលបានផ្តល់ឱ្យ k ។

ឧទាហរណ៍

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

ការពន្យល់

ត្រូវការតែ ១ ស្វបប៉ុណ្ណោះ។ ៦ អាចដោះដូរបានជាមួយ ២ ដូច្នេះ ៤, ២, ១ និង ៣ មកជាមួយគ្នា។

ក្បួនដោះស្រាយ

  1. រាប់ចំនួនធាតុទាំងអស់ដែលតិចជាង k ។
  2. រាប់ចំនួនធាតុដែលធំជាង k ។
  3. កំណត់ទិន្នផលទៅតម្លៃតូចជាង។
  4. ឆ្លងកាត់អារេពី i = 0 និង j = រាប់។
    1. ពិនិត្យមើលថាអារេ [i] ធំជាងតម្លៃ k បន្ទាប់មកបន្ថយតម្លៃតូចជាង ១ ។
    2. ពិនិត្យមើលថាអារេ [j] ធំជាងតម្លៃ k បន្ទាប់មកបង្កើនតំលៃតូចជាង ១ ។
    3. ស្វែងយល់ពីអប្បបរមារវាងទិន្នផលនិងតូចជាងមុនហើយផ្ទុកវាទៅលទ្ធផល។
  5. ត្រឡប់តម្លៃនៃលទ្ធផល។

ការពន្យល់

យើងបានផ្តល់ឱ្យ អារេ of ចំនួនគត់និងតម្លៃចំនួនគត់ហៅថា k យើងបានស្នើឱ្យរកការដោះដូរអប្បបរមាចំនួនប៉ុន្មានដើម្បីទទួលបានធាតុទាំងអស់ដែលនៅតិចជាងឬស្មើ k ។ ចងចាំថាយើងគ្រាន់តែត្រូវការរកការផ្លាស់ប្តូរអប្បបរមា។

ចំពោះបញ្ហានេះយើងនឹងរាប់ចំនួនធាតុដែលតូចជាងឬស្មើ k ហើយរក្សាទុកវាទៅអថេរតូចជាង។ ដូច្នេះអថេរតូចជាងនេះនឹងរាប់ចំនួនតូចជាងដែលតូចជាងឬស្មើ k ។ ប្រហាក់ប្រហែលនឹងការរាប់នោះដែរយើងរាប់លេខទាំងអស់ដែលធំជាងលេខ k ។ កំណត់តម្លៃនៃទិន្នផលឱ្យតូចជាងនេះនៅពេលក្រោយយើងនឹងប្រៀបធៀបតម្លៃជាមួយនឹងលទ្ធផលនេះហើយបន្តរក្សាទុកវាក្នុងពេលដំណាលគ្នា។ ប្រសិនបើយើងយកឧទាហរណ៍មួយដែលត្រូវបានលើកឡើងខាងលើ 4 គឺជាចំនួនតូចជាងហើយលេខ 1 គឺជាចំនួនធំជាង។

បញ្ច្រាសអារេដោយយក i = 0, j = តូចជាង, ពិនិត្យមើលអារេ [i] និងមកដល់ [j] ធំជាងតំលៃ k, បើមកដល់ [ខ្ញុំ] ធំជាង, បន្ថយចំនួនតូចជាងបើអារេ [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

កូដចាវ៉ាដើម្បីរកការផ្លាស់ប្តូរអប្បបរមាដែលត្រូវការដើម្បីនាំធាតុទាំងអស់តិចជាងឬស្មើ 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” គឺជាចំនួនធាតុក្នុងអារេ។ ពីព្រោះយើងបានដំណើរការរង្វិលជុំដែលមិនមានរង្វិលជុំ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១) ដោយមិនចាំបាច់មានទំហំបន្ថែម។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺថេរ។