本文共 1888 字，大约阅读时间需要 6 分钟。

问题

在O（n）时间和O（1）额外空间中重新排列正数和负数

数组包含随机数的正数和负数。重新排列数组元素，以便交替放置正数和负数。正数和负数的数量不必相等。如果有更多正数，它们将出现在数组的末尾。如果还有更多的负数，它们也会出现在数组的末尾。

如果输入数组为[-1、2，-3、4、5、6，-7、8、9]，则输出应为[9，-7、8，-3、5，- 1，2，4，6]

解决

思路

1，想象一个坐标系，左边都是负数，右边都是正数，有一个虚拟的坐标0

第一步先把所有负数正数按照坐标系排布，大小不考虑 第二步，将坐标按照要求替换即可 不需要创建新数组，时间复杂度和空间复杂度都符合

package array;import java.util.Arrays;/** * @ClassName Make02 * Description TODO **/public class Make02 {       public static void main(String[] args) {           int[] arr1 = {   -1, -2,-3,-4,1,2,3,4,8};        int count=0,temp=0;        for (int i = 0; i < arr1.length; i++) {               if (arr1[i]<0) {                  temp =arr1[count];               arr1[count]=arr1[i];               arr1[i]=temp;               count++;            }        }        System.out.println(Arrays.toString(arr1));        int mytemp=0;        for (int i = 0; i*2+1 <=count &&count+2*i

接下来可以不看

1，假设有数组A

int[] arr1 = {   2,1, 3, -4,5,-6,7,8}

先设定一个空数组B，与A等长

第一遍扫描所有负数，第二次扫描所有正数放在第一次扫描的后面 这样形成一个坐标轴结构，只要根据坐标规则相互替换就行 然而这样开辟了两个空间，不符合，但是可以写，没兴趣可以不继续看 另外一种算法是先将正数坐标扫描到B中，再添加负数坐标 遍历A数组，查看A数组长度为奇数还是偶数（决定后面的数据如何添加，即数组坐标如何计算） 然后将A数组中为正数的放置在B上，坐标规则为2i

将2i坐标超出A长度的,在末尾回退添加 按照案例推理出来的，自己可以算算 A长度为奇数，回退算法是：A.length-2i-2，算出来要覆盖的坐标

A的长度为偶数，回退坐标算法：A.length-(2i+1)，算出来要覆盖的坐标 比如图中的元素6，A数组长度为6，偶数,6不小于A的长度，因此需要回退，6-20-1=5，覆盖第五个坐标

在扫描正数的同时可以扫描负数，原理同正数

添加元素的规则是2i+1 如果负数元素很多，计算回退坐标是 A长度为奇数，回退算法是：A.length-(2i-1)，算出来要覆盖的坐标

A的长度为偶数，回退坐标算法：A.length-2i-2，算出来要覆盖的坐标

package array;import java.util.Arrays;/** * @ClassName Make01 * Description TODO **/public class Make01 {       public static void main(String[] args) {           int[] arr1 = {   2,-1, -3, -4,-5,-6,7,8},arr2=new int[arr1.length];        int iCountG=0,iGreater=0,iLess=0,iLessL=0,flag_even=0;        if (arr1.length%2==0) {               flag_even=1;        }        for (int i = 0; i < arr1.length; i++) {               if (arr1[i]>=0) {                   if (iGreater*2