内容简介:有一个整形数组,包含正数和负数,然后要求把数组内的所有负数移至正数的左边,且保证相对位置不变,要求时间复杂度为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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。