如何在线性时间内通过绝对值重新排序已排序的数组？

Question

如何在线性时间内通过绝对值重新排序已排序的数组？

4

给你一个包含负数和正数的已排序数组。重新排列数组，将负数取绝对值。时间复杂度应为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

11个回答

1

可以通过考虑以下3种情况来完成：

a. 所有正数：保持数组不变

b. 所有负数：反转数组

c. 正数和负数都有：在输入数组中找到最后一个负数，然后使用左右比较。

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

0

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

你的复杂度应该是O(n)。但你现在是O(n^2)。 - Yan Khonski

0

@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

那不是问题所在。初始数组已经排序。为什么数字会混合呢？所有负数将是连续的，然后是所有正数。 - Zoso

0

这里有一个快速解决方案

将列表分为两部分，第一部分包含负数，第二部分包含正数

应用合并算法来合并两个列表。例如在C#中：

List<int> neg = arr.Where(x => x < 0).Reverse().ToList();
List<int> pos = arr.Where(x => x > 0).ToList();
var res=merge(neg,pos);    

 private static List<int> merge(List<int> left, List<int> right)
      {
          List<int> result = new List<int>();

          while (left.Count > 0 || right.Count > 0)
          {
              if (left.Count > 0 && right.Count > 0)
              {
                  if (Math.Abs(left.First()) <= right.First())  
                  {
                      result.Add(left.First());
                      left.Remove(left.First());     
                  }
                  else
                  {
                      result.Add(right.First());
                      right.Remove(right.First());
                  }
              }
              else if (left.Count > 0)
              {
                  result.Add(left.First());
                  left.Remove(left.First());
              }
              else if (right.Count > 0)
              {
                  result.Add(right.First());

                  right.Remove(right.First());
              }
          }
          return result;
      }

- Sandeep

0

你可以用一行Python代码实现

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

print(sorted(nums,key=abs))

输出结果将会是：

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

- ashok

0

<?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

0

双指针算法。

void resort(vector<int> &a){

   int par ; // partition index (when +ve elements starts)

   // lets find where positive elements starts
   for(int i = 0; i < a.size(); i++){
      if(a[i] >= 0) {
         par = i;
         break;
      }
   }

  int l = par-1; // left of par
  int r = par;   // right side

  vector<int> b; // extra array for answer

 
  // compare left and right side element
  // if any of them is lesser push that element in extra array i.e 'b'
  while(l >= 0 and r < a.size()) {

     if(abs(a[l]) > a[r]) {
        b.push_back(a[r]);
        r++;
     }
     else if(abs(a[l]) < a[r]){
        b.push_back(a[l]);
        l--;
     }
     else{
        b.push_back(a[l]);
        l--;
     }
  }

 // push remaing element from both side
 // like merge sort

  while(l >= 0) {
    b.push_back(a[l]);
    l--;
  }
  while(r < a.size()) {
     b.push_back(a[r]);
     r++;
  }

  // print modified answer
  for(auto x:b) {
     cout<<x<<" ";
  }
}

时间复杂度 O(N)

空间复杂度 O(N)

- Manish Sharma

感谢您提供这段代码片段，它可能会提供一些有限的、即时的帮助。一个适当的解释将极大地提高其长期价值，因为它可以展示为什么这是一个好的问题解决方案，并使其对未来读者在其他类似问题上更有用。请[编辑]您的答案以添加一些解释，包括您所做的假设。 - jasie

0

这是Python的代码

    def sorted_array(list1):
        list_negative=[]
        list_positive=[]

        for i in list1:
        if i<0:
            list_negative.append(i)
        else:
            list_positive.append(i)

        list_negative.reverse()    

        for i in list_negative:
            for j in range(0, len(list_positive)):
                if abs(i)<=list_positive[j]:
                    list_positive.insert(j,i)
                    break
        print(list_positive)    
    list1=[-8,-5,-3,-1,3,6,9,-4]    
    sorted_array(list1)

- Sachin Jakhar

0

你可以简单地使用冒泡排序来实现这个功能

 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

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- thefourtheye · Accepted Answer

将数组分成两半，一半是负数，另一半是正数。
反转负数的数组。
然后，使用两个数组的绝对值运行合并算法。

总体运行时间复杂度仍为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" />