Я должен отсортировать список номеров, но я супер ленивый. Очень сложно понять, как поменять местами все числа, пока они не будут в порядке возрастания, поэтому я разработал собственный алгоритм, который будет гарантировать сортировку нового списка ». Вот как это работает:

Для списка размера N нам понадобится N-1 итераций. На каждой итерации

• Проверьте, меньше ли N-й номер, чем N + 1-й номер. Если это так, то эти два числа уже отсортированы, и мы можем пропустить эту итерацию.

• Если это не так, то вам нужно постоянно уменьшать первые N чисел, пока эти два числа не будут в порядке.

Давайте возьмем конкретный пример. Допустим, вход был

10 5 7 6 1

На первой итерации мы сравним 10 и 5. 10 больше 5, поэтому мы уменьшаем его до тех пор, пока оно не станет меньше:

4 5 7 6 1

Теперь мы сравним 5 и 7. 5 меньше, чем 7, поэтому нам не нужно ничего делать на этой итерации. Итак, мы переходим к следующему и сравниваем 7 и 6. 7 больше 6, поэтому мы уменьшаем первые три числа до 6, и получаем:

2 3 5 6 1

Теперь мы сравниваем 6 и 1. Опять же, 6 больше 1, поэтому мы уменьшаем первые четыре числа до тех пор, пока оно не станет меньше 1, и мы получим это:

-4 -3 -1 0 1

И мы сделали! Теперь наш список в идеальном порядке. И, чтобы сделать вещи еще лучше, нам нужно было только перебирать список N-1 раз, так что этот алгоритм сортирует списки за O (N-1) время, которое, я уверен, является самым быстрым алгоритмом.

Ваша задача на сегодня - реализовать эту Ленивую Сорт. Ваша программа или функция получит массив целых чисел в любом стандартном формате, который вам нравится, и вы должны выполнить эту отложенную сортировку и вернуть новый «отсортированный» список. Массив никогда не будет пустым или содержит нецелые числа.

Вот некоторые примеры:

Input: 10 5 7 6 1
Output: -4 -3 -1 0 1

Input: 3 2 1
Output: -1 0 1

Input: 1 2 3
Output: 1 2 3

Input: 19
Output: 19

Input: 1 1 1 1 1 1 1 1 1 
Output: -7 -6 -5 -4 -3 -2 -1 0 1 

Input: 5 7 11 6 16 2 9 16 6 16
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16

Input: -8 17 9 7
Output: -20 5 6 7

Как всегда, это код-гольф , поэтому напишите самую короткую программу, какую только сможете!

¹ Это не означает, что это звучит, как это означает, но это технически верно

² Я шучу, пожалуйста, не ненавидь меня

Желе ,  14 12 11  9 байт

-2 байта благодаря ETHproductions (используйте минимальную диаду, «)

I’«0Ṛ+\Ṛ+

Монадическая ссылка, берущая и возвращающая списки целых чисел.

Попробуйте онлайн! или посмотрите набор тестов .

Я действительно не думаю, что этого достаточно Lazy ™!

Как?

I’«0Ṛ+\Ṛ+ - Link: list of integers, a              e.g. [ 8, 3, 3, 4, 6, 2]
I         - increments between consecutive items of a   [-5, 0, 1, 2,-4 ]
 ’        - decrement (vectorises)                      [-6,-1, 0, 1,-5 ]
   0      - literal 0
  «       - minimum of decremented increments and zero  [-6,-1, 0, 0,-5 ]
    Ṛ     - reverse                                     [-5, 0, 0,-1,-6 ]
      \   - cumulative reduce with:
     +    -   addition                                  [-5,-5,-5,-6,-12]
       Ṛ  - reverse                                     [-12,-6,-5,-5,-5]
        + - addition (with a)                           [-4,-3,-2,-1, 1, 2]

Haskell , 40 байт

f(a:r)|h:t<-f r=h-max(r!!0-a)1:h:t
f x=x

Попробуйте онлайн!

JavaScript (ES6), 61 байт

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

Контрольные примеры

let f =

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

console.log(JSON.stringify(f([10, 5, 7, 6, 1]))) // -4 -3 -1 0 1
console.log(JSON.stringify(f([3, 2, 1]))) // -1 0 1
console.log(JSON.stringify(f([1, 2, 3]))) // 1 2 3
console.log(JSON.stringify(f([19]))) // 19
console.log(JSON.stringify(f([1, 1, 1, 1, 1, 1, 1, 1, 1]))) // -7 -6 -5 -4 -3 -2 -1 0 1
console.log(JSON.stringify(f([5, 7, 11, 6, 16, 2, 9, 16, 6, 16]))) // 27 -25 -21 -20 -10 -9 -2 5 6 16
console.log(JSON.stringify(f([-8, 17, 9, 7]))) // -20 5 6 7

Желе , 12 байт

I»1U
0ị;Ç_\U

Попробуйте онлайн!

Как это работает

I»1U  Helper link. Argument: l (list of integers)
I     Compute the increments (difference between items) of l.
 »1   For each item n, take the maximum of n and 1.
   U  Reverse.

0ị;Ç_\U  Main link. Argument: l (list of integers)
   Ç     Call the helper link with argument l.
  ;      Concatenate this with
0ị       the 0th last item of the (1-indexed) l. (Can't use Ṫ because it modifies l)
    _\   Cumulatively reduce the result by subtraction.
      U  Reverse.

Основная идея в игре заключается в следующем: если вы инвертируете входной и выходной массивы, выводом будет просто ввод с каждой дельтой 0 или более, замененной -1. Например:

[10,  5,  7,  6,  1]   input
[ 1,  6,  7,  5, 10]   reverse
[   5,  1, -2,  5  ]   deltas
[  -1, -1, -2, -1  ]   min(deltas, -1)
[ 1, -1, -2, -1, -1]   reverse and concat the last item of the original
[ 1,  0, -2, -3, -4]   re-apply deltas
[-4, -3, -2,  0,  1]   reverse

к, 20 байтов

{x-|+\0,1_0|1+-':|x}

Попробуйте онлайн.

Объяснение:

{                  } /function, x is input
                 |x  /reverse x
              -':    /difference between every element
            1+       /add one to each difference
          0|         /make minimum difference be 0
      0,1_           /swap first difference with a 0
    +\               /cumulative sum
   |                 /reverse again
 x-                  /subtract from x

Haskell, 56 байт

a#(x:y:z)=map(+min(y-x-1)0)(a++[x])#(y:z)
a#x=a++x
([]#)

Попробуйте онлайн!

Оставьте первую часть списка в параметре a. На каждом шаге добавляйте следующий элемент xв конец aи увеличивайте все элементы до минимума (y-x-1)и 0.

Python , 54 байта

f=lambda a,*r:r and[f(*r)[0]-max(r[0]-a,1)]+f(*r)or[a]

Попробуйте онлайн!

Принимает входной splatted как f(1,2,3). Выводит список. Использует экспоненциальное время.

C #, 76 байт

a=>{for(int d=0,i=a.Length-1;i>0;a[--i]-=d)d=a[i-1]-d<a[i]?d:a[i-1]-a[i]+1;}

Это изменяет список на месте. Он проходит по списку в обратном порядке и сохраняет промежуточную сумму дельты для каждого числа.

JavaScript (ES6), 59 байт

f=([n,...a],p=a[0]-n)=>a+a?[(a=f(a))[0]-(p>1?p:1),...a]:[n]

Brain-Flak , 153 байта

{(({})<>[({})])(({}({}))[({}[{}])])<>(([{}]({})))([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}{{}({}<>{}())((<>))}{}{}}{}<>{}([]){{}({}<>)<>([])}<>

Попробуйте онлайн!

Это включает в себя +1для -rфлага.

#While True
{

    #Push the last value left in the array minus the counter onto the alternate stack
    (({})<>[({})])

    #Put the counter back on top of the alternate stack
    (({}({}))[({}[{}])])

    #Toggle
    <>

    #Find the difference between the last two inputs left on the array
    (([{}]({})))

    #Greater than or equal to 0?
    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

    #If So:
    {

      #Pop the truthy/falsy value
      {}

      #Increment the counter by the difference between elements +1
      ({}<>{}())

      #Push two falsys
      ((<>))

    #Endwhile
    }

    #Pop the two falsys
    {}{}

#Endwhile
}

#Pop the falsy

{}

#Toggle back
<>

#Pop the counter

#Reverse the stack
{}
([]){{}({}<>)<>([])}<>

R, 56 байт

function(s){s-c(rev(cumsum(rev(pmax(0,-diff(s)+1)))),0)}

JavaScript (ES6), 68 байт

a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

Вход и выход - это массив целых чисел.

Тестовый фрагмент

f=
a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

<input id=I oninput="O.value=f(this.value.split` `.map(x=>+x)).join` `">
<input id=O disabled>

JavaScript (ES6), 50 байт

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

Объяснение:

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

Функция вызывает себя до тех пор, пока какие-либо элементы не работают. Когда элементы окончательно отсортированы, клон возвращается. (Мы не можем вернуть сам массив, потому что some()метод уменьшил бы все его элементы, отключив их на -1.)

Тестовые случаи:

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

console.log(f([10,5,7,6,1])+'');
console.log(f([1,1,1,1,1,1,1,1,1])+'');
console.log(f([5,7,11,6,16,2,9,16,6,16])+'');
console.log(f([19])+'');
console.log(f([-8,17,9,7])+'');
console.log(f([1,2,3,4,5,6,7])+'');

SWI-Пролог, 194 байта

:-use_module(library(clpfd)).
f([],[],_,_).
f([A|B],[M|N],P,D):-A#=M-D-E,A#<P,abs(M,S),T#=S+1,E in 0..T,label([E]),f(B,N,A,D+E).
l([],[]).
l(A,B):-reverse(Z,B),f([X|Y],Z,X+1,0),reverse(A,[X|Y]).

Может быть в состоянии попробовать это онлайн здесь: http://swish.swi-prolog.org/p/LazySort.pl

Вы спрашиваете, l(L, [10,5,7,6,1]).что говорит "решить для L, где L - ленивый вариант этого списка".

Две функции:

• lazysorted (A, B) - указывает, что A является lazysorted версией B, если они оба являются пустыми списками, или если A можно получить путем обращения B, вызова вспомогательной функции для обхода списка и выполнения вычитания с помощью аккумулятора толкая каждое значение ниже, чем предыдущее, и возвращая результат обратно вправо.
• fпомощник сопоставляет два списка, значение предыдущего числа в списке и накопитель скользящей разности, и решает, для нового значения текущей позиции списка, являющегося исходным значением минус накопитель разности, опционально минус новое значение, требуемое для принудительной установки этого значения. значение ниже предыдущего числа в списке, и fдолжно быть рекурсивно вычислено для конца списка с теперь увеличенным аккумулятором разницы.

Скриншот тестовых случаев на Swish:

JavaScript (ES6), 61 байт

a=>a.reduceRight((r,e)=>[e-(d=(c=e-r[0]+1)>d?c:d),...r],d=[])

Не самое короткое решение, но я не мог упустить возможность использовать reduceRight.

C # (.NET Core) , 89 88 86 79 байтов

• Сохранено всего 1 байт с немного другим подходом.
• Сохранено еще 2 байта с упрощением fors.
• Сохранено 7 байтов благодаря удивительным навыкам игры в гольф VisualMelon.

a=>{for(int i=0,j,k;++i<a.Length;)for(k=a[i-1]-a[j=i]+1;--j>=0;)a[j]-=k>0?k:0;}

Попробуйте онлайн!

Сначала forвыполняется итерация по массиву, затем вычисляется уменьшение и, наконец, второе, forпри необходимости, уменьшение элементов до iпозиции th.

Допустимо ли просто изменить исходный массив вместо возврата нового (все еще привыкая к правилам)?