Перемещение элементов массива

Question

Считать, что первые n-1 элементов массива упорядочены по неубыванию (каждый элемент со 2-го до предпоследнего (n-1-го) больше или равен своего левого соседа). Определить, в каком месте массива должен оказаться последний (n-й) элемент и вставить его на соответствующую, наибольшую возможную, позицию. Вывести на экран номер этой позиции и измененный массив.

Другого массива не использовать

Answer 1

Первым шагом определяете место вставки (в простом случае используете линейный поиск, в более продвинутом сценарии используете бинарный поиск, раз вам сказано, что массив сортированный, вам нужен вариант алгоритма BinarySearch RightMost, т.к.элементы могут повторяться).

Шаг два - сделать in place shift массива на один элемент вверх, чтобы освободить место под вставку.

void Main()
{
    var arr = new int[] {1,2,2,2,2,2,4,5,6,7,3};
    Process(arr).Dump();
    arr.Dump();
}

// You can define other methods, fields, classes and namespaces here


public int Process(int[] arr)
{
    var target = arr[arr.Length - 1];
    var insertionPoint = BinarySearchRightmost(arr, target) + 1;
    $"insertionPoint {insertionPoint} => {arr[insertionPoint]}".Dump();
    ShiftUpArray(arr, insertionPoint);
    arr[insertionPoint] = target;
    return insertionPoint;
}

public int BinarySearchRightmost(int[] nums, int target)
{
    if (nums == null)
        return -1;

    var left = 0;
    var right = nums.Length;

    while (left < right)
    {
        var mid = left + (right - left) / 2;

        if (nums[mid] <= target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }

    return right - 1;
}

public void ShiftUpArray(int[] arr, int start)
{
    for (int i = arr.Length - 1; i >= start; i--)
    {
        arr[i] = arr[i-1];
    }
}

Например:

var arr = new int[] {1,2,2,2,2,2,4,5,6,7,3};
Process(arr).Dump();
arr.Dump();

Вывод:

То же самое будет и в случае если вставляем двойку - она вставится в конец двоек:

var arr = new int[] {1,2,2,2,2,2,4,5,6,7,2};
Process(arr).Dump();
arr.Dump();

БЛОГ НА HUSL

Перемещение элементов массива

Ответы (1 шт):