Как отсортировать только часть массива? между заданными индексами - PullRequest
Новая
       65

Как отсортировать только часть массива? между заданными индексами

1 голос
/ 11 июля 2020

У меня есть массив чисел, и мне нужно отсортировать только его часть по левому и правому барьерам. Не могли бы вы помочь мне, как правильно его реализовать? 

const sortBetween = (arr, left, right) => {
   ...
}
given: [9,3,5,7,4,9,4,1] , left = 2, right = 5
expected: [9,3,4,5,7,9,4,1]

[9,3, 5,7,4,9 , 4,1] -> [9,3, 4,5,7,9 , 4,1]

Спасибо за помощь.

Ответы [ 3 ]

1 голос
/ 11 июля 2020

Вы можете сделать это, используя метод Divide and Conquer . Вы можете попробовать это - 

const sortBetween = (arr, left, right) => {
  let leftArr = [],
    rightArr = [],
    sortedArr = [];
    
  /**
   * Divide the array into 3 parts. Left, Mid, Right.
   * You have to sort the mid one.
   */
  
  if (left > 0) {
     leftArr = arr.slice(0, left);
  }
  
  if (right < arr.length) {
    rightArr = arr.slice(right);
  }
  
  sortedArr = arr.slice(left, right).sort();
  
  // Finally merge the 3 parts and returns
  return [...leftArr, ...sortedArr, ...rightArr];
}

const arr = [9,3,5,7,4,9,4,1];

const res = sortBetween(arr, 2, 5);
const res1 = sortBetween(arr, 0, 5);
const res2 = sortBetween(arr, 0, 8);

console.log(res, res1, res2);
.as-console-wrapper {min-height: 100%!important; top: 0}
1 голос
/ 11 июля 2020

Это подход с использованием sort напрямую, но с формированием доступа с помощью Proxy для length и индексов. 

  type        original array       length
-------  ------------------------  ------
values    9  3  5  7  4  9  4  1       8
indices   0  1  2  3  4  5  6  7
-------  ------------------------  ------

  type          proxy view         length
-------  ------------------------  ------
values          5  7  4  9             4
indices         0  1  2  3
-------  ------------------------  ------


const
    sortBetween = (array, left, right) => {
        new Proxy(array, {
            get (target, prop) {
                if (isFinite(prop)) return target[+prop + left];
                if (prop === 'length') return right - left + 1;
                return target[prop];
            },
            set (target, prop, receiver) {
                target[+prop + left] = receiver;
                return true;
            }
        })
        .sort((a, b) => a - b);

        return array;
    };    
    
console.log(...sortBetween([9, 3, 5, 7, 0, 9, 4, 1], 2, 5)); // [9, 3, 0, 5, 7, 9, 4, 1]
1 голос
/ 11 июля 2020

Финал (надеюсь): 

newArr = [].concat(
  arr.slice(0,left),
  arr.slice(left,right+1).sort(),
  arr.slice(right+1,arr.length)
)

взятие right включительно, предполагая, что левый не больше правого, предполагая, что массив не пуст, et c.

Предыдущее редактирование: Прочитал комментарии. В основном правильно. Проблема, которую я наблюдал, заключалась в том, что запрошенная сортировка выполняется между левым и правым включительно , тогда как первый аргумент slice равен включительно , а второй аргумент - исключительный .

Я вижу, теперь последняя часть должна быть отрицательной величиной, разницей между левой и длиной массива. Но я не буду пытаться решить эту проблему ...

Мой исходный «ответ»: Я предлагаю вам разделить массив на 3 подмассива, используя slice, отсортировать середину, а затем снова собрать их, используя concat, например: 

newArr=[].concat(arr.slice(0,left),arr.slice(left,right+1).sort(),arr.slice(left+right-1))

Могу я предложить вам получить больше знакомы с slice и concat при поиске в Интернете?

...