给定一组正负整数,重新排列它,使得一端为正整数,另一端为负整数.

Question

我最近遇到了一个面向软件工程师的微软面试问题.

给定一组正负整数,重新排列它,使得一端为正整数,另一端为负整数,但保留原始数组中的出现顺序.

例如,给出[1, 7, -5, 9, -12, 15]
的答案是:[-5, -12, 1, 7, 9, 15]

这应该在O(n)中完成.

我们可以很容易地在O(n)中完成它,但我无法想象我们如何能够像原始数组一样维护元素的顺序.如果我们忘记O(n)的复杂性,有人可以告诉我如何在不考虑空间和时间复杂性的情况下保持元素的顺序.

编辑:在实际问题中,我们还需要具有O(1)空间复杂度.

Answer 1

要在恒定空间(但是二次时间)内实现此结果,可以通过在数组的每一端放置一个队列来使用双队列方法(类似于荷兰国旗算法).从左到右读取项目:向左侧队列添加项目意味着不管它,将项目添加到右侧队列意味着将不在队列中的所有元素向左移动一个并将添加的项目放在最后.然后,要连接队列,只需反转第二个队列中元素的顺序.

这执行O(n)操作(向左移位元件)直到O(n)次,这产生O(n 2)运行时间.

通过使用类似于合并排序的方法,您可以实现更低的O(n log n)复杂度:将数组分成两半,在表单中递归排序[N P] [N P]然后在O(n)时间内将第一个P与第二个交换N(它当它们没有完全相同的尺寸时会变得有点棘手,但它仍然是线性的.

我完全不知道如何把它降到O(n)时间.

编辑:实际上,您的链表清单是正确的.如果数据是作为双向链表提供的,则可以在O(n)时间O(1)空间中实现双队列策略:

sort(list):
  negative = empty
  positive = empty
  while (list != empty)
     first = pop(list)
     if (first > 0) 
         append(positive,first)
     else
         append(negative,first)
  return concatenate(negative,positive)

使用链表实现来保持指向第一个和最后一个元素的指针,然后pop,append和concatenate都是O(1)操作,因此总复杂度为O(n).至于空间,没有任何操作分配任何内存(追加只使用pop释放的内存),所以它总体上是O(1).

Answer 2

这是O(n)时间O(1)空间解的一个constriant版本,它假设maxValue*(maxValue + 1)小于Integer.MAX_VALUE,其中maxValue是maxmum值减去数组中minmum值的结果.它利用原始数组作为临时数组来存储结果.

public static void specialSort(int[] A){
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for(int i=0; i<A.length; i++){
        if(A[i] > max)
            max = A[i];
        if(A[i] < min)
            min = A[i];
    }
    //Change all values to Positive
    for(int i=0; i<A.length; i++)
        A[i]-= min;

    int newMax = max-min+1;

    //Save original negative values into new positions
    int currNegativeIndex = 0;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax < (-min))
            A[currNegativeIndex++] += (A[i]%newMax)*newMax;
    //Save original positive values into new positions
    int currPositiveIndex = currNegativeIndex;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax > (-min))
            A[currPositiveIndex++] += (A[i]%newMax)*newMax;
    //Recover to original value 
    for(int i=0; i<A.length; i++){
        A[i] = A[i]/newMax + min; 
    }
}

Answer 3

我不确定我是否正确理解了这个问题,因为答案看起来太简单了:

• 遍历数组并计算负数 - O(n)
• 创建一个大小为O(n)的新数组
• 遍历原始数组并将数字放入新数组中.使用已知数量的负数来抵消正数 - O(n)

这是在Python中快速完成的方法.它与上面略有不同,首先为负片创建一个数组,然后附加正数.所以它不那么有效,但仍然是O(n).

>>> a = [1,7,-5,9,-12,15]
>>> print [x for x in a if x < 0] + [y for y in a if y >= 0]
[-5, -12, 1, 7, 9, 15]

编辑:好的,现在有了O(1)空间复杂性,它变得更加困难.我对如何在O(n)时间复杂度中实现它感兴趣.如果它有帮助,这是一种保持O(1)空间复杂度的方法,但需要O(n ^ 2)时间复杂度:

• 从最左边的负数开始.遍历阵列,直到找到下一个负数.
• 在新循环中,将负数与其左侧的正数进行交换.这样做直到你到达其他负数.这确保了数字的顺序保持不变.
• Rince并重复,直到找到新的负数时到达数组的末尾.

Answer 4

它可以在O(n)和空间O(1)中完成.

我们需要在阵列中扫描3次并仔细更改一些值.

假设:大小为N的数组中的最大值应小于(N+1) * Integer.MAX_VALUE.

我们需要这个假设,因为我们很好地改变了数组中的一些正值.

• 在第一次扫描中,找到负值和正值的#,以及最大值.
• 在第二次扫描中,我们创建数组的负部分,如下所示:

我们从数组的开头开始,我们将第一个找到的正数(例如在索引处)与第一个找到的负数" 交换 " i(例如j).由于负数正在考虑其位置,因此交换是可以的.

问题是正数,因为在i和之间可能还有一些其他正数j.为了解决这个问题,我们必须在交换之前以某种方式编码该值中正数的索引.那么我们就可以意识到它在第一点的位置.我们可以做到这一点a[i]=(i+1)*(max)+a[i].

• 在第三次扫描中,我们创建了数组的正部分.在第二次扫描结束时,构造负数组,并且正数移位到右侧,但它们的位置可能不正确.因此,我们通过它并纠正他们的位置,因为这些信息被编码了他们的价值.

这是代码:

import java.util.Arrays;

public class LinearShifting {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = {-1,7,3,-5,4,-3,1,2};
        sort(a);
        System.out.println(Arrays.toString(a));  //output: [-1, -5, -3, 7, 3, 4, 1, 2]
    }
    public static void sort(int[] a){
        int pos = 0;
        int neg = 0;
        int i,j;
        int max = Integer.MIN_VALUE;
        for(i=0; i<a.length; i++){
            if(a[i]<0) neg++;
            else pos++;
            if(a[i]>max) max = a[i];
        }
        max++;
        if(neg==0 || pos == 0) return;//already sorted
        i=0;
        j=1;
        while(true){
            while(i<=neg && a[i]<0) i++;
            while(j<a.length && a[j]>=0) j++;
            if(i>neg || j>=a.length) break;
            a[i]+= max*(i+1);
            swap(a,i,j);
        }

        i = a.length-1;
        while(i>=neg){
            int div = a[i]/max;
            if(div == 0) i--;
            else{
                a[i]%=max;
                swap(a,i,neg+div-2);// minus 2 since a[i]+= max*(i+1);
            }
        }

    }
    private static void swap(int[] a, int i , int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}