Что дальше/предыдущее?

LeetCode Еженедельный конкурс 138 довольно простой, и вы можете сказать из 3-го вопроса… 1053. Предыдущая перестановка с одной перестановкой.

1053. Предыдущая перестановка с одной перестановкой

Учитывая массив A положительных целых чисел (не обязательно различных), верните лексикографически наибольшую перестановку, меньшую, чем A, которую можно выполнить с помощью одной замены (перестановка меняет местами два числа A[i] и A[j]). Если это невозможно сделать, верните тот же массив.

Итак, что мы хотим получить…

[3,2,1] → [3,1,2]
[1,1,5] → [1,1,5]
[1,9,4,6,7] → [1,7,4,6,9]
[3,1,1,3] → [1,3,1,3]

Если числа восходящие, например [1,2,3] или [1,1,5], то у него нет предыдущего числа.

Если числа не восходящие, чтобы получить его предыдущий номер, нам нужно зациклиться с конца и найти первое число, начиная с которого оно не является восходящим. Например, если это [2,1,2,3], мы обнаружили, что первая «2» — это число.

Затем, чтобы получить первое предыдущее число [2,1,2,3], нам нужно поменять местами «2» и «1». Тогда получаем ответ [1,2,2,3]. Другой пример: [1,9,4,6,7], мы обнаружили, что «9» — это первое не восходящее число, и мы поменяли его местами с «7».

С каким номером мы поменяемся местами? Оно должно быть меньше, чем «не восходящее число» в массиве восходящих.

Давайте попробуем примеры выше:

[3,2,1] → [2], [1] → [3,1,2]
[1,1,5] → [] → [1,1,5]
[1,9,4,6,7] → [9], [7] → [1,7,4,6,9]
[3,1,1,3] → [3], [1] → [1,3,1,3]

Теперь нам просто нужно преобразовать алгоритм в код

var prevPermOpt1 = function(A) {
    let turnIdx;
    let i = A.length-1;
    while(!turnIdx && i>0){
        if(A[i]<A[i-1]) turnIdx = i-1;
        i--;
    }
    
    const lastPart = A.slice(turnIdx+1);
    let swapIdx;
    let j = lastPart.length - 1;
    while(!swapIdx && j>-1){
        if(lastPart[j] < A[turnIdx]) swapIdx = turnIdx + j + 1;
        j--;
    }
    
    function swap(a,b, arr){
        const temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        
        return arr;
    }
    
    return swap(turnIdx, swapIdx, A);
};

Эта проблема точно соответствует логике 31. Следующая перестановка.

31. Следующая перестановка

Реализуйте следующую перестановку, которая переставляет числа в лексикографически следующую большую перестановку чисел.

Если такое расположение невозможно, оно должно быть переупорядочено как самый низкий возможный порядок (т. е. отсортировано в порядке возрастания).

Замена должна быть на месте и использовать только постоянную дополнительную память.

Вот несколько примеров. Входы находятся в левом столбце, а соответствующие им выходы — в правом столбце.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

В этой задаче есть еще одно требование: поменять местами числа, если нет следующей перестановки.

var nextPermutation = function(nums) {
    let i = nums.length - 1;
    let rightPeak = null;
    while(i>-1 && !rightPeak){
        if(nums[i] > nums[i-1]) rightPeak = i;
        i--;
    }
    
    
    if(i=== -1){
        reverse(0)
    } else {
        let leftNeighbor = rightPeak - 1;
        
        let i = nums.length - 1;
        let greaterThanLeftNeighbor = null;
        while(i>-1 && !greaterThanLeftNeighbor){
            if(nums[i]>nums[leftNeighbor]) greaterThanLeftNeighbor = i;
            i--;
        }
        
        swap(leftNeighbor, greaterThanLeftNeighbor, nums);
        
        reverse(rightPeak);
    }
    
    function swap(a, b, arr){
        arr[a] = arr[a]^arr[b];
        arr[b] = arr[a]^arr[b];
        arr[a] = arr[a]^arr[b];
    }
    
    function reverse(start){
        let end = nums.length - 1;
        let n = Math.floor((end - start + 1)/2);
        while(n--){
            swap(start, end, nums);
            start++;
            end--;
        }
    }
    
    return nums;
};