Мінімальний обмін, необхідний для об’єднання всіх елементів, менших або рівних 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 = count.
    1. Перевірте, чи масив [i] не перевищує значення k, тоді зменште значення менше на 1.
    2. Перевірте, чи масив [j] не перевищує значення k, тоді збільште значення менше на 1.
    3. Знайдіть мінімум між вихідним та меншим і збережіть його для виведення.
  5. Повернути значення виводу.

Пояснення  

Ми дали масив of цілих чисел, і ціле значення, що називається k, ми попросили з’ясувати, скільки мінімальних обмінів потрібно, щоб отримати всі елементи разом, які менше або дорівнюють k. Пам'ятайте, нам потрібно лише знайти мінімальний обмін.

Дивись також
Перетворення Postfix в Infix

Для цього ми збираємося підрахувати кількість елементів, яка менше або дорівнює k, і збережемо її меншою змінною. Отже, менша змінна буде містити кількість менших чисел, які менше або дорівнюють k. Подібно до цього підрахунку, ми підраховуємо всі числа, більші за число k. Встановіть значення виходу на менше, пізніше ми будемо порівнювати значення з цим результатом і продовжувати зберігати в ньому одночасно. Якщо взяти приклад, згаданий вище, 4 - кількість менших, а 1 - більших.

Перемістіть масив, приймаючи i = 0, j = менше, перевірте масив [i] і arr [j] більше значення k, якщо arr [i] більше, то зменшіть кількість менших, якщо масив [j] більше, ніж збільшити кількість менших.

Одночасно ми знайдемо мінімум між вихідним та меншим числом, у циклі, який ми проходимо, ми виконуємо обидві операції, щоб зменшити значення меншого і збільшити значення меншого. Нарешті, нам просто потрібно повернути значення виводу. Тому що це буде мати бажаний вихід.

Мінімальний обмін, необхідний для об’єднання всіх елементів, менших або рівних k

код  

Код С ++ для пошуку мінімальних обмінів, необхідних для об'єднання всіх елементів, менших або рівних 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

Аналіз складності  

Складність часу

О (п) де "n ” - кількість елементів у масиві. Тому що у нас були цикли запуску, які не мали вкладених циклів. Таким чином, часова складність є лінійною.

Дивись також
Знайти суму масивів, що не повторюються (різні)

Складність простору

O (1) оскільки додатковий простір не потрібен. Тож космічна складність є постійною.