设任意n个整数存放于数组a(1:n)中,试编写算法,将所有正数排在所有负数前面(要求算法时间复杂度为o(n))
时间: 2023-04-21 21:03:41 浏览: 186
算法步骤如下:
1. 定义两个指针i和j,分别指向数组a的第一个元素和最后一个元素。
2. 当i<j时,执行以下循环:
a. 如果a[i]为正数,i++。
b. 如果a[j]为负数,j--。
c. 如果a[i]为负数,a[j]为正数,交换a[i]和a[j]的值,i++,j--。
3. 循环结束后,所有正数都排在了所有负数的前面。
算法时间复杂度为O(n),因为只需要遍历一次数组。
相关问题
数据结构中设任意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--;
}
}
}
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)