内容简介:有一个整形数组,包含正数和负数,然后要求把数组内的所有负数移至正数的左边,且保证相对位置不变,要求时间复杂度为O(n), 空间复杂度为O(1)。例如,{10, -2, 5, 8, -4, 2, -3, 7, 12, -88, -23, 35}变化后是{-2, -4,-3, -88, -23,5, 8 ,10, 2, 7, 12, 35}。实现原理是:两个变量记录左右节点,两边分别开始遍历。左边的节点遇到负值继续前进,遇到正值停止。右边的节点正好相反。然后将左右节点的只进行交换,然后再开始遍历直至左右节点相遇
问题描述:
有一个整形数组,包含正数和负数,然后要求把数组内的所有负数移至正数的左边,且保证相对位置不变,要求时间复杂度为O(n), 空间复杂度为O(1)。例如,{10, -2, 5, 8, -4, 2, -3, 7, 12, -88, -23, 35}变化后是{-2, -4,-3, -88, -23,5, 8 ,10, 2, 7, 12, 35}。
解决方法
实现原理是:两个变量记录左右节点,两边分别开始遍历。左边的节点遇到负值继续前进,遇到正值停止。右边的节点正好相反。然后将左右节点的只进行交换,然后再开始遍历直至左右节点相遇。
这种方式的时间复杂度是O(n).空间复杂度为O(1)
以下为 java 的实现:
public void setParted1(int[] a, int left, int right) {
if (left >= right || left == a.length || right == 0) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
return;
}
while (a[left] < 0) {
left++;
}
while (a[right] >= 0) {
right--;
}
if (left >= right || left == a.length || right == 0) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
return;
}
swap(a, left, right);
left++;
right--;
setParted1(a, left, right);
}
private void swap(int a[], int left, int right) {
int temp = 0;
temp = a[left];
a[left] = a[right];
a[right] = temp;
}
热度: 2
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
The Sovereign Individual
James Dale Davidson、William Rees-Mogg / Free Press / 1999-08-26 / USD 16.00
Two renowned investment advisors and authors of the bestseller The Great Reckoning bring to light both currents of disaster and the potential for prosperity and renewal in the face of radical changes ......一起来看看 《The Sovereign Individual》 这本书的介绍吧!