在数组中交替使用正数和负数

Question

给定一个正数和负数（没有零）的数组，我必须以这样的方式排列它们：正数和负数应该连续排列。

正数和负数的数量可能不相等，也就是说，如果没有正数（或负数），那么所有剩余的负数（或正数）都会追加到数组的末尾。

顺序很重要，即如果输入数组是{2，-1，-3，-7，-8,9,5，-5，-7}，那么输出数组应该是{2，-1,9，-3,5，-7，-8，-5，-7}。代码在O（n）中完成，而不使用另一个数组。

这是我在java中的解决方案，我再次测试了几个案例并成功了。但是，我不确定这是否在O（n）时间内运行。基本上，我先计算正数和负数的数量。然后我有两个索引i=0和j=1。j总是领先i一步。从那里我继续检查i中的数字是否为正，j是否为负，如果不是，i将遍历数组，直到我找到正确位置的下一个正/负并将其移动到正确位置。

任何建议都将不胜感激。谢谢

//array of negative and positive, arrange them so that positive number follow by negative
// if no pos or neg left, the rest append to the array. 
//should be O(n) no additional array
public static void alter(int[] a) {
    int pos = 0;
    int neg = 0;
    int index = 0;
    while (c < a.length) {
        if (a[index] > 0) {
            pos++;
        } else neg++;
        index++;
    }

    int i = 0;
    int j = 1;
    int temp = 0;
    //run until no more positive number or negative number
    while (pos > 0 && neg > 0) {
        //
        if (a[i] > 0) {
            pos--;
            if (a[j] < 0) {
                i += 2;
                j += 2;
                neg--;
            } else // a[j] > 0
            {
                while (a[j] > 0) {
                    j++;
                }
                //a[j] < 0
                neg--;
                //move that number to the appropriate place 
                while (j > i) {
                    temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                    j--;
                } // end while
                i += 2;
                j += 2;
            }
        } else // a[i] < 0
        {
            while (a[i] < 0) {
                i++;
            }
            //a[i] > 0
            //move that number to the appropriate place 
            while (i > (j - 1)) {
                temp = a[i];
                a[i] = a[i - 1];
                a[i - 1] = temp;
                i--;
            }

        } //end else    
    }

}

Answer 1

PFB我的代码。如果我们将使用Stack，那么它将使我们的问题更容易。

public class AlternatePosNeg {
public static void main(String[] args) {
    int arr[] = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };

    Stack<Integer> pos = new Stack<>();
    Stack<Integer> neg = new Stack<>();

    int i;

    for (i = 0; i < arr.length; i++) {
        if (arr[i] > 0) {
            pos.push(arr[i]);
        } else {
            neg.push(arr[i]);
        }
    }

    int tempArr[] = new int[arr.length];

    i = 0;

    int sizePos = pos.size();
    int sizeNeg = neg.size();

    while (i < tempArr.length) {
        if (sizePos > sizeNeg) {
            if (pos.size() > 0) {
                tempArr[i] = pos.pop();
            }
            if (neg.size() > 0) {
                tempArr[i + 1] = neg.pop();
                i++;
            }
        } else {
            if (neg.size() > 0) {
                tempArr[i] = neg.pop();
            }
            if (pos.size() > 0) {
                tempArr[i + 1] = pos.pop();
                i++;
            }
        }

        i++;
    }

    for (int no : tempArr) {
        System.out.print(no + " ");
    }
}

}

Answer 2

是的，它可以在O（n）中完成。

假设c是当前位置。a[c]是正数。

1）从c向数组末尾递增i，直到i指向第一个错误的数字（与前一个符号相同的数字，在本例中为正）。

2） 设置j:=i；

3）在数组末尾增加j，直到j指向带有通号的数字（在本例中为负）。

4）将[i]与[j]交换。

5）设置c：=j；

6）设置j：=c 1；

在每一步中，你总是增加i、j或c，而不是减少。变量i的增量不能超过n倍。与j和c相同。

所以最大增量是3n~O（n）。

Answer 3

但是，我不确定这是否在O（n）时间内运行

我不认为它在O（n）中运行。当您必须“找到下一个正确的元素并将其移动到正确的位置”时，您需要

1. 循环数组的其余部分。这意味着，在最坏的情况下（数组开始时包含所有正元素，结束时包含所有负元素），您将在数组中“未排序”部分的一半上再循环一次每个正元素
2. 将图元移回正确位置时，可以逐个位置移动它。这意味着您可以在数组的“未排序”部分上再次循环

如果您需要遵守在不使用第三个数组的情况下必须遵守排序的要求，那么还不确定如何在O（n）中运行它。