Переставить массив так, чтобы arr [i] = i

Question

Input : arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
Output : [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]

Input : arr = {19, 7, 0, 3, 18, 15, 12, 6, 1, 8,
              11, 10, 9, 5, 13, 16, 2, 14, 17, 4}
Output : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
         11, 12, 13, 14, 15, 16, 17, 18, 19]

Подход 1. Перемещение по массиву.

Проверьте, если a [i] = -1, если да, игнорируйте его. Если a [i]! = -1, проверьте, находится ли элемент a [i] в ​​правильном положении (i =А [я]).Если да, то игнорируйте его.

Если a [i]! = -1 и элемент a [i] не в правильном положении (i! = A [i]), тогда поместите его в егоправильная позиция, но есть два условия:

(i). Любой A [i] свободен, означает A [i] = -1, затем просто поместите A [i] = i.

(ii). ИЛИ A [i] не является вакантным, означает A [i] = x, тогда int y = x положить A [i] = i.Теперь нам нужно поместить y в правильное место, поэтому повторите процедуру с шага 3.

Какова будет временная сложность решения ниже?

public static int[] fix(int[] A) {
    for (int i = 0, x = A[i]; i < A.length; i++) {
        if (x == -1 || x == i)
            continue;

        // check if desired place is not vacant
        while (A[x] != -1 && A[x] != x) {
            int y = A[x];   // store the value from desired place
            A[x] = x;       // place the x to its correct position
            x = y;          // now y will become x, now search the place for x
        }

        A[x] = x;           // place the x to its correct position

        // check if while loop hasn't set the correct value at A[i]
        if (A[i] != i)
            A[i] = -1;      // if not then put -1 at the vacated place
    }

    return A;
}

Answer 1

Я могу предложить вам два алгоритма.

Первый: с использованием дополнительного массива, сложность времени составляет O(n), с O(n) дополнительной памятью

public static int[] fix(int[] arr) {
    int[] res = new int[arr.length];

    Arrays.fill(res, -1);

    for (int i = 0; i < arr.length; i++)
        if (arr[i] != -1)
            res[arr[i]] = arr[i];

    return res;
}

Второй: на месте, сложность времени O(n^2) в худшем случае и O(n) в среднем, без дополнительной памяти

public static int[] fix(int[] arr) {
    int i;

    while ((i = findIncorrectPosition(arr)) >= 0) {
        while (arr[i] != -1 && arr[i] != i) {
            swap(arr, i, arr[i]);
        }
    }

    return arr;
}

... плюс два частных метода поддержки:

private static int findIncorrectPosition(int[] arr) {
    for (int i = 0; i < arr.length; i++)
        if (arr[i] != -1 && arr[i] != i)
            return i;
    return -1;
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}