已知线性表(a1,a2, a3 ,…,an)按顺序存于内存,每个元素都是整数,试设计用最少时间把所有值为负数的元素移到全部非负数值元素前边的算法:例:(x,-x,-x,x,x,-x …x)变为(-x,-x,-x…x,x,x)。
时间: 2024-06-12 11:06:59 浏览: 6
解法一:双指针法
设两个指针i和j,初始时i指向第一个元素,j指向最后一个元素。在移动指针过程中,如果a[i]为负数,就将a[i]和a[j]交换位置,同时j指向前一个元素;如果a[i]为非负数,则i指向下一个元素。直到i和j相遇,算法结束。
时间复杂度为O(n),空间复杂度为O(1)。
代码实现:
void moveNegative(int a[], int n) {
int i = 0, j = n - 1;
while(i < j) {
if(a[i] < 0) {
swap(a[i], a[j]);
j--;
} else {
i++;
}
}
}
解法二:快排思想
将所有负数视为小于0的元素,非负数视为大于等于0的元素。可以使用快排的思想,将小于0的元素全部移到数组前面,大于等于0的元素全部移到数组后面。
时间复杂度为O(nlogn),空间复杂度为O(logn)。
代码实现:
void quickSort(int a[], int left, int right) {
if(left >= right) return;
int i = left, j = right, pivot = a[left];
while(i < j) {
while(i < j && a[j] >= pivot) j--;
if(i < j) a[i++] = a[j];
while(i < j && a[i] < pivot) i++;
if(i < j) a[j--] = a[i];
}
a[i] = pivot;
quickSort(a, left, i - 1);
quickSort(a, i + 1, right);
}
void moveNegative(int a[], int n) {
quickSort(a, 0, n - 1);
}
注意:如果只需要将负数移到前面,而不需要保证负数的相对位置不变,那么可以使用快排的partition函数,只需要将小于0的元素移到前面即可。时间复杂度为O(n),空间复杂度为O(1)。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)