Что дальше/предыдущее?
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; };