Минимальные свопы, необходимые для объединения всех элементов, меньших или равных 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. Проверьте, больше ли array [i] значения k, затем уменьшите значение меньше на 1.
    2. Проверьте, больше ли array [j] значения k, затем увеличьте значение меньше на 1.
    3. Найдите минимум между выводом и меньшим и сохраните его для вывода.
  5. Вернуть значение вывода.

объяснение

Мы дали массив of целые, и целочисленное значение, называемое k, мы попросили выяснить, сколько минимальных свопов требуется, чтобы собрать вместе все элементы, которые меньше или равны k. Помните, что нам нужно найти только минимальные свопы.

Для этого мы собираемся подсчитать количество элементов, которые меньше или равны k, и сохранить его в меньшей переменной. Таким образом, меньшая переменная будет содержать количество меньших чисел, которые меньше или равны k. Подобно этому счету, мы считаем все числа, которые больше числа k. Установите значение вывода на меньшее, позже мы будем сравнивать значения с этим выводом и продолжать сохранять в нем одновременно. Если мы возьмем пример, который был упомянут выше, 4 - это счет меньшего, а 1 - счет большего.

Пройдите по массиву, взяв i = 0, j = меньше, проверьте array [i] и arr [j] больше, чем значение k, если arr [i] больше, то уменьшите счетчик меньших if array [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

Анализ сложности

Сложность времени

О (п) в котором  п » - количество элементов в массиве. Потому что у нас были циклы выполнения, в которых не было вложенных циклов. Таким образом, временная сложность линейна.

Космическая сложность

O (1) так как дополнительное пространство не требуется. Так что сложность пространства постоянна.