设任意n个整数存放于数组A(1:n)中,试编写算法,将所有正数排在所有负数前面(要求算法复杂度为0(n))。(难度系数2)
时间: 2024-05-19 16:14:33 浏览: 17
可以采用双指针的方法,一个指针指向数组的开头,一个指针指向数组的末尾,然后从两端向中间扫描。
当左指针指向的数为负数且右指针指向的数为正数时,交换两个数的位置,然后继续向中间扫描。
当左指针指向的数为正数时,左指针向右移动一位。
当右指针指向的数为负数时,右指针向左移动一位。
直到左指针和右指针相遇为止,所有正数就排在了所有负数前面。
下面是具体的实现代码:
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void rearrange(int A[], int n)
{
int left = 0, right = n - 1;
while (left < right)
{
while (left < right && A[left] > 0)
left++;
while (left < right && A[right] < 0)
right--;
if (left < right)
swap(A[left], A[right]);
}
}
相关问题
数据结构中设任意n个整数存放于数组A(1:n)中,试编写算法,将所有正数排在所有负数面前
好的,这是一个关于数据结构的问题,我会尽力回答。可以使用双指针的方法,一个指向数组的开头,一个指向数组的结尾,从两端开始遍历数组,如果左边是负数,右边是正数,则交换它们的位置。重复这个过程直至两个指针相遇。以下是具体的实现代码:
```python
def rearrange_array(arr):
left = 0
right = len(arr) - 1
while left < right:
while arr[left] < 0:
left += 1
while arr[right] >= 0:
right -= 1
if left < right:
arr[left], arr[right] = arr[right], arr[left]
return arr
```
这个算法的时间复杂度为O(n),因为只需要遍历整个数组一次。
设任意n个整数存放于数组a(1:n)中,试编写算法,将所有正数排在所有负数前面(要求算法复杂度为0(n))。
算法步骤如下:
1. 定义两个指针i和j,分别指向数组a的第一个元素和最后一个元素。
2. 当i<j时,执行以下操作:
a. 如果a[i]为正数,则i自增1。
b. 如果a[j]为负数,则j自减1。
c. 如果a[i]为负数且a[j]为正数,则交换a[i]和a[j]的值,然后i自增1,j自减1。
3. 当i>=j时,算法结束。
代码实现如下:
void rearrange(int a[], int n) {
int i = , j = n - 1;
while (i < j) {
if (a[i] > ) {
i++;
} else if (a[j] < ) {
j--;
} else {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
}
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)