Можно ли реализовать «Меньшие числа, чем текущие», используя один запрос LINQ?

Question

Делал эту проблему https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/submissions/

Ввод: nums = [8,1,2,2,3]

Выход: [4 , 0,1,1,3]

Объяснение: Для чисел [0] = 8 существует четыре меньших числа, чем оно (1, 2, 2 и 3). Для чисел [1] = 1 не существует ни одного меньшего числа, чем оно. Для чисел [2] = 2 существует одно меньшее число, чем оно (1). Для чисел [3] = 2 существует одно меньшее число, чем оно (1). Для чисел [4] = 3 существует три меньших числа, чем оно (1, 2 и 2).

как LINQ-y, насколько это возможно, и придумал решение, которое является только половиной LINQ :(

public class Solution {
    public int[] SmallerNumbersThanCurrent(int[] nums) {

        var groups = nums
            .Select((val, index) => new { index, val })
            .GroupBy(x => x.val)
            .OrderBy(g => g.Key)
            .Select(g => g.Select(x => x.index).ToArray());

        var arr = new int[nums.Length];

        int numSmaller = 0;

        foreach (var indices in groups)
        {
            foreach (var index in indices)
            {
                arr[index] = numSmaller;
            }

            numSmaller += indices.Length;
        }

        return arr;
    }
}

Кто-нибудь здесь достаточно умен, чтобы помочь мне найти путь к LINQ - если вторая половина решения? Предпочтительно O (n log n) как код, который я имею.

Answer 1

Хотя я не думаю, что использование одного LINQ является хорошей идеей, можно избавиться от foreach, который у вас есть, при условии, что требуется приблизительный nlog (n) :

nums.Select((num, index) => new { num, index })
        // order number
        .OrderBy(x => x.num)
        // select number with their original index in nums and 
        // their order in the ordered collection
        .Select((x, order) => new { x.num, x.index, order })
        // Group the result by number
        .GroupBy(x => x.num)
        // Consolidate order in the ordered collection by selecting the minimum
        // possible order
        .Select(g => new
        {
            numWithOrder = g.Select(_ => new
            {
                num = _,
                minOrder = g.First().order
            })
        })
        // Flatten the collection
        .SelectMany(g => g.numWithOrder)
        // There should be minOrder number of results in the original collection
        // are smaller than the number
        .Select(x => new { x.num.index, result = x.minOrder })
        // Restore as per original index
        .OrderBy(x => x.index)
        // Select final result
        .Select(x => x.result)

Как вы могли видеть, LINQ убивает удобочитаемость кода.

Answer 2

Надеюсь, я понял ваш вопрос. Вы можете сделать следующее.

public int[] SmallerNumbersThanCurrent(int[] nums)
{
    return nums.Select(x=> nums.Count(c=> c<x)).ToArray();
}

Answer 3

Вот еще одно решение. Он использует метод расширения Scan из пакета System.Interactive для подсчета путем накопления чисел, которые меньше, чем номера текущей группы.

public int[] SmallerNumbersThanCurrent(int[] nums)
{
    return nums
        .Select((x, i) => (Item: x, Index: i))
        .GroupBy(x => x.Item, x => x.Index)
        .OrderBy(g => g.Key)
        .Scan(seed: (Indices: Enumerable.Empty<int>(), Counter: 0),
            accumulator: (acc, x) => (x, acc.Counter + acc.Indices.Count()))
        .SelectMany(acc => acc.Indices,
            (acc, element) => (Index: element, CountOfSmallerNumbers: acc.Counter))
        .OrderBy(x => x.Index)
        .Select(x => x.CountOfSmallerNumbers)
        .ToArray();
}

Это решение, возможно, еще более неясное и нечитаемое, чем решение Вейхча . 101

Подпись метода расширения Scan:

public static IEnumerable<TAccumulate> Scan<TSource, TAccumulate>(
    this IEnumerable<TSource> source, TAccumulate seed,
    Func<TAccumulate, TSource, TAccumulate> accumulator);

Генерирует последовательность накопленных значений путем сканирования исходной последовательности и применения функции аккумулятора.

Answer 4

public int[] SmallerNumbersThanCurrentShorter(int[] nums)
{
  return (from x in nums select (from y in nums where y < x select y).Count()).ToArray();
}

просто сделай это !!

Answer 5

Очевидное решение O (n ^ 2) с прямым решением, которое считает числа меньше текущего:

 var result = nums.Select(x => nums.Count(v => v < x)).ToList();

Еще одно безумное решение с одним оператором O (n log n) с двойной сортировкой с использованием Aggregate. Сначала, чтобы увидеть, сколько элементов «меньше», чем любой заданный - O (n log n), затем правильно учесть повторяющиеся элементы - O (n), и, наконец, второй вид, чтобы вернуть порядок к нормальному - O (n log n):

var r = nums.Select((Value, Position) =>new {Value,Position})
    .OrderBy(x=> x.Value)
    .Select((x,i) => new { x.Value, x.Position, CountLess = i })
    .Aggregate(
       new { list = Enumerable.Repeat(
           new { Value = 0, Position = 0, CountLess = 0 },0) , prev = -1, shift = 0 },
       (acc, cur) =>
           acc.prev == -1 ?
             new { list = acc.list.Concat(new[] { cur }), prev = cur.Value, shift = 0 } :
             new
                  {
                     list = acc.list.Concat(new[] 
                        { new { cur.Value, cur.Position,
                           CountLess = cur.CountLess - (acc.prev == cur.Value ? 
                             acc.shift + 1 : 0) } }),
                     prev = cur.Value,
                     shift = acc.prev == cur.Value ? acc.shift + 1 : 0
                  })
    .list
    .OrderBy(x => x.Position)
    .Select(x => x.CountLess);