Интересное задание codewars.com

[Белый шум]

https://javascript.ru/forum/misc/734...tml#post483544 - кто-нибудь пробовал решить?

function smaller(arr) {
   return arr.map(
     (cur, i) => arr.slice(i+1).reduce(
       (sum, cur1) => {
         return (cur1 < cur) ? sum+1 : sum;
       }, 0
     )
   );
}

console.log(smaller([5, 4, 3, 2, 1]), '[4, 3, 2, 1, 0]');
console.log(smaller([1, 2, 3]), '[0, 0, 0]');
console.log(smaller([1, 2, 0]), '[1, 1, 0]');
console.log(smaller([1, 2, 1]), '[0, 1, 0]');
console.log(smaller([1, 1, -1, 0, 0]), '[3, 3, 0, 0, 0]');
console.log(smaller([5, 4, 7, 9, 2, 4, 4, 5, 6]), '[4, 1, 5, 5, 0, 0, 0, 0, 0]');

Не гурман, поэтому никаких послевкусий ))

[j0hnik]

шум, братец, не все так просто для этой каты решающий фактор скорость.
и даже без использование абстракций (что быстрей как минимум вдвое) не прокатывает =(

function smaller(arr) {
		var newArr = [], x = arr.length;
			for (var i = 0; i<x; i++){
			var s = 0;
			for(var j = i; j<x; j++){
				s = (arr[j] < arr[i]) ? s+1 : s;
			}
			newArr[i]=s;
		}
		return newArr;
	}

Alexandroppolus, тут решение наверное кардинально другое?

[Aetae]

j0hnik, у меня мысль примерно также шала, только вместо for - обратные while - меньше буков и иногда быстрее.
Можно ещё добавить "кэш" - сохранять количество и позицию для для конкретной цифры и если таковая нашлась на следующих итерациях - не проходить весь цикл заново, а только до той позиции, прибавляя предыдущий результат и обновляя кэш. Это даст выигрыш в случае множества повторов.
Но в решении не было изюминки, слишком оно в лоб, а потому врядли требуемое, так что я плюнул.)

[j0hnik]

Aetae,
а while это конечно копейки.
а вот кеш это идея, там массивы по 80000 - 100000 length значения -1000 - 1000

[Aetae]

С кэшем примерно так, но как и ожидалось - не проходит

function smaller(arr) {
  var length = arr.length, 
      i = length, j, 
      result = new Array(length),
      cache = Object.create(null);
  while (i--){
    if(arr[i] in cache){
      j = cache[arr[i]];
      cache[arr[i]] = i;
      result[i] = result[j];
    }else{
      cache[arr[i]] = i;
      result[i] = 0;
      j = length;
    }
    while(--j > i)
      if(arr[j] < arr[i]) 
        result[i]++;
  }
  return result;
}

Нужен какой-то трюк.)

...можно ещё запоминать максимальное число и минимальное, в первом случае - просто прибавлять оставшуюся длину, во втором ставить ноль. Но это всё рост "вширь", а надо, думается в глубину.)

[j0hnik]

Aetae,
Истина где-то рядом!
Проснется подскажет

[j0hnik]

Но это всё рост "вширь", а надо, думается в глубину.)

да, там как минимум еще тройной прирост нужен, это вряд ли спасет

[Alexandroppolus]

тут решение наверное кардинально другое?

Разумеется, очевидный вложенный цикл не прокатит, как его не оптимизируй
А всё из-за квадратичной сложности. Да, асимптотика здесь рулит.

В качестве подсказки - правильное решение имеет сложность O(n*ln(n)), что на порядки быстрее при данных объёмах.

[j0hnik]

function smaller(arr) {
	var n = arr.length, node = null, result, newArr = new Array(n);
	function addTo(node, value, smallerCount){
		if(node === null) { //старт
			node = { value: value, lowerCount: 0, count: 1, left: null, right: null }; 
			result = smallerCount;
		}
		else if(node.value === value){ // баланс 
			node.count++;
			result = smallerCount + node.lowerCount;
		}
		else if(value < node.value){ 
			node.lowerCount++;
			node.left = addTo(node.left, value, smallerCount);
			// дублирующее количество правых +1
		}
		else node.right = addTo(node.right, value, smallerCount + node.count + node.lowerCount); // количество меньших чисел
		return node;
	}
	for(var i = n-1; i >= 0; i--) {
		node = addTo(node, arr[i], 0);
		newArr[i] = result;
	}
	return newArr;
}

лучше шестерки под чаек решать, чем так загоняться

[Alexandroppolus]

j0hnik,
Чтобы юзеры не слишком загонялись, автор задачи специально не стал добавлять более-менее отсортированные массивы, и можно обойтись обычным бинарным деревом без всяких там балансировок )

А шестерки надоедают быстро, какие-то они все однообразные.