一道字节算法题
- 链接：算法连贯
- 起源：牛客网
- 把数组元素依照正负序重排列
- 给定一个数组，数组它依照上面的规定重排列后的数组：1. 数组中的正负数互相距离 2. 符号雷同的数字绝对程序不变 3. 如果某种符号的数字多余，放到数组最初
- 例如：-1,3,2,4,5,-6,7,-9
- 重排列后：3,-1,2,-6,4,-9,5,7
- 空间复杂度要求 O(1)
解决思路：
既然要求空间复杂度为为 O(1)级别那只能用双指针进行排序了。
咱们遍历数组，交替的地寻找下一个负数 / 正数, 记该数地位为 j, 将它插入到数组的以后地位 i，并把数组 [i~j] 的元素往后移即可。
public void sortPosAndNeg(int[] array){
// 正负数索引地位
int pos = 0, neg = 0;
// 用 flag 来标记以后要插入的是负数还是正数
boolean flag = true;
for (int i = 0; i < array.length; i++) {if (flag){
// 从数组以后地位开始查找下一个负数
pos = i;
while (pos < array.length && array[pos] < 0){pos++;}
// 找不到下一个负数，阐明排序完了
if (pos >= array.length) break;
// 后移，先取出要插入的数
int res = array[pos];
for (int j = pos; j > i; j--) {array[j] = array[j-1];
}
array[i] = res;
flag = false;
}else {
neg = i;
while (neg < array.length && array[neg] > 0){neg++;}
if (neg >= array.length) break;
// 后移
int res = array[neg];
for (int j = neg; j > i; j--) {array[j] = array[j-1];
}
array[i] = res;
flag = true;
}
}
}