Вопрос:

Как я могу пересортировать отсортированный массив по абсолютным значениям, по линейному времени?

javascript arrays sorting

3776 просмотра

7 ответа

927 Репутация автора

Вам дан отсортированный массив, содержащий как отрицательные, так и положительные значения. Прибавьте массив, принимая абсолютное значение отрицательных чисел. Ваша сложность должна быть O (n)

Пример ввода

[-8, -5, -3, -1, 3, 6, 9]

Ожидаемый результат

[ -1, -3, 3, -5, 6, -8, 9 ]

Я делал это до сих пор, но вывод не правильный.

function sortMe(input) {
   var newArr = [];
   for (var i = 0; i < input.length; i++) {
     var value = Math.abs(input[i]);
     newArr.push(value);
   }
   var c = newArr.sort()
}

и это дает вывод

[ 1, 3, 3, 5, 6, 8, 9 ]
Автор: Bhushan Goel Источник Размещён: 30.05.2015 06:50

Ответы (7)


7 плюса

170789 Репутация автора

  1. Разбейте массив на две половины, одну с отрицательными числами, а другую с положительными числами.

  2. Обратный массив отрицательных чисел.

  3. Затем запустите алгоритм слияния с абсолютным значением обоих массивов.

Общая сложность во время выполнения все еще O (n).


function sortMe(sortedArray) {

  var idx = -1, negs, pos, result = [], nIdx = 0, pIdx = 0;

  if (sortedArray.length === 0)
    return result;

  // Find the index where positive elements begin
  while (idx < sortedArray.length && sortedArray[++idx] < 0);

  // Get elements till the index and reverse the array
  negs = sortedArray.slice(0, idx).reverse();

  // Get elements from the index till the end
  pos = sortedArray.slice(idx);

  // Merging algorithm implementation which merges `negs` and `pos`
  while (nIdx < negs.length || pIdx < pos.length)
  {
    if (nIdx < negs.length && pIdx < pos.length)
    {
      if (Math.abs(negs[nIdx]) <= pos[pIdx])
        result.push(negs[nIdx++]);
      else
        result.push(pos[pIdx++]);
    }
    else if (nIdx < negs.length)
      result.push(negs[nIdx++]);
    else
      result.push(pos[pIdx++]);
  }

  return result;
}

console.log(sortMe([-8, -5, -3, -1, 3, 6, 9]));
// [ -1, -3, 3, -5, 6, -8, 9 ]

function sortMe(sortedArray) {

  var idx = -1, negs, pos, result = [], nIdx = 0, pIdx = 0;

  if (sortedArray.length === 0)
    return result;

  // Find the index where positive elements begin
  while (idx < sortedArray.length && sortedArray[++idx] < 0);

  // Get elements till the index and reverse the array
  negs = sortedArray.slice(0, idx).reverse();

  // Get elements from the index till the end
  pos = sortedArray.slice(idx);

  // Merging algorithm implementation which merges `negs` and `pos`
  while (nIdx < negs.length || pIdx < pos.length)
  {
    if (nIdx < negs.length && pIdx < pos.length)
    {
      if (Math.abs(negs[nIdx]) <= pos[pIdx])
        result.push(negs[nIdx++]);
      else
        result.push(pos[pIdx++]);
    }
    else if (nIdx < negs.length)
      result.push(negs[nIdx++]);
    else
      result.push(pos[pIdx++]);
  }

  return result;
}

function getElement(id) {
  return document.getElementById(id);
}

function sorter() {
  var data = getElement("numbers").value.split(" ").map(Number);
  getElement("result").innerHTML = "[" + sortMe(data).join(", ") + "]";
}
<input id="numbers" value="-8 -5 -3 -1 3 6 9" />
<input type="button" onclick="sorter()" value="Click here to Sort" />
<pre id="result" />

Автор: thefourtheye Размещён: 30.05.2015 06:53

0 плюса

47 Репутация автора

Может быть сделано с учетом 3 случаев:

а. Все положительные числа: оставить массив как есть

б. Все отрицательные числа: обратный массив

с. Положительные и отрицательные числа: найдите последнее отрицательное число во входном массиве, а затем используйте левое и правое сравнение.

import java.util.Arrays;

public class SortAbsoluteValue {
    // all positive; all negative; postive & negative
    public static void main(String[] args) {
        int[] num = new int[] { -8, -5, -3, -1, 3, 6, 9 };
        int[] result = sortAbsolute(num);

        for (int i = 0; i < num.length; i++) {
            System.out.println(result[i]);
        }
    }

    private static int[] sortAbsolute(int[] num) {
        int size = num.length;
        // all positive : leave as is
        if (num[0] >= 0)
            return num;
        // all negative : reverse array
        if (num[size-1] < 0) {
            int[] temp = Arrays.copyOf(num, num.length);
            Arrays.sort(temp);
            return temp;
        }
        int[] result = new int[size];

        int i = 0;
        for (i = 0; i < size - 1; i++) {
            if (num[i] < 0 && num[i + 1] >= 0) {
                break;
            }
        }

        int left = i - 1;
        int right = i + 1;
        result[0] = num[i];
        int k = 0;
        while (left >= 0 && right < size) {
            if (Math.abs(num[left]) < num[right]) {
                result[++k] = num[left];
                left--;
            } else {
                result[++k] = num[right];
                right++;
            }
        }
        // remaining left elements, if any
        while(left>=0) {
            result[++k] = num[left--];
        }
        // remaining right elements, if any
        while(right<size) {
            result[++k] = num[right++];
        }
        return result;
    }
}
Автор: Abhay Размещён: 14.06.2015 08:32

0 плюса

81 Репутация автора

@thefourtheye, ваше решение очень хорошее, но оно не исправляет последовательности номеров процессов, где числа (положительные и отрицательные) смешаны. Вы можете проверить свое решение с помощью следующей последовательности, например: [-2 -5 3 8 -10], и это даст вам неверный результат: [3, -5, -2, 8, -10].

Это потому что:

1) Вы полагаете, что отрицательные и положительные числа должны идти в отсортированном порядке.

2) Найти индексы положительных и отрицательных чисел, несмотря на то, что они могут идти непоследовательно.

Я исправил ваш код, и теперь он может обрабатывать любые смешанные последовательности положительных / отрицательных чисел и правильно сортировать их по абсолютным значениям. Код ниже:

function sortArrayByAbsValues(sortedArray) {

                var negs = [], pos = [], result = [], nIdx = 0, pIdx = 0;

                if (sortedArray.length === 0)
                    return result;

                //prepare negative/positive number sequences.
                for (var i = 0; i < sortedArray.length; i++) {
                    var value = sortedArray[i];
                    if (value < 0) {
                        negs.push(value);
                    } else {
                        pos.push(value);
                    }
                }
                // sort positive/negative numbers
                pos = pos.sort();
                negs = negs.sort();

                // Merging algorithm implementation which merges `negs` and `pos`
                while (nIdx < negs.length || pIdx < pos.length) {
                    if (nIdx < negs.length && pIdx < pos.length) {
                        if (Math.abs(negs[nIdx]) <= pos[pIdx])
                            result.push(negs[nIdx++]);
                        else
                            result.push(pos[pIdx++]);
                    }
                    else if (nIdx < negs.length)
                        result.push(negs[nIdx++]);
                    else
                        result.push(pos[pIdx++]);
                }

                return result;
            }
Автор: Aleksey Borodkin Размещён: 28.01.2016 11:01

0 плюса

26 Репутация автора

inputArray.sort(function(a,b) {
    return Math.abs(a) - Math.abs(b);
});

Может не быть O (N), но работал хорошо для меня

Автор: brickfungus Размещён: 17.10.2016 04:32

0 плюса

1 Репутация автора

Вы можете просто достичь этого, используя Bubble sort

 var array= new Array(2,-2,3,5,-3,1);

 function absoluteSortin(array){

    var inputArray= array.slice(0);
    var temp;

    for(var i=0;i< inputArray.length;i++){
        for(j=i+1; j<inputArray.length;j++){
            if(Math.abs(inputArray[i]) > Math.abs(inputArray[j])){
                temp= inputArray[j];
                inputArray[j] = inputArray[i];
                inputArray[i] = temp;
            }
        }
    }
   return inputArray;

 }
 absoluteSortin(array);
Автор: Akhilesh.tiwari Размещён: 28.12.2017 03:51

0 плюса

16 Репутация автора

<?php
$a = array(-2,-3,0,5,4,1,6,9,7,-9,-1,3);
for($i=0;$i<count($a)-1;$i++) {
    for($j=0;$j<count($a)-1;$j++){
        $data1=abs($a[$j]);
        $data2=abs($a[$j+1]);
        if($data1>$data2) {
            $temp = $a[$j];
            $a[$j] = $a[$j+1];
            $a[$j+1] = $temp;
        }
    }
}
echo "<pre>";
print_R($a);
?>
Автор: Suruchi Babbar Размещён: 17.03.2018 08:44

0 плюса

1 Репутация автора

        int[] arr = new int[] { -8, -5, -3, -1, 3, 6, 9 };
        for(int i =0; i < arr.Length; i++)
        {
            int pos = 0;                
            for (int j = 0; j < arr.Length; j++)
            {
                if (Math.Abs(arr[pos]) > Math.Abs(arr[j]))
                {
                    int temp;
                    temp = arr[pos];
                    arr[pos] = arr[j];
                    arr[j] = temp;
                    pos++;
                }
            }

        }
Автор: amit verma Размещён: 13.06.2019 05:32
Вопросы из категории :
32x32