设有长度为n的一维整型数组A,设计一个算法,将该数组中所有的负数存放在 数组的前部,而所有的正数存放在负数的后面。
时间: 2023-05-11 15:03:53 浏览: 172
可以使用双指针法,一个指针从数组的左端开始,另一个指针从数组的右端开始,分别向中间移动,当左指针指向的元素为负数,右指针指向的元素为正数时,交换两个元素的位置,直到两个指针相遇为止。具体实现代码如下:
void partition(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) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
}
}
}
相关问题
设有长度为n的一维整型数组,设计一个算法,将该数组中所有的负数存放在数组的前部,而所有的正数存放在负数的后面。
可以使用双指针法,一个指针从数组的左端开始,一个指针从数组的右端开始,分别向中间移动。当左指针指向的数为负数,右指针指向的数为正数时,交换两个数的位置。直到左指针和右指针相遇为止,这样就可以将负数和正数分别放在数组的前部和后部。
c++已知具有n个数组元素的一维数组a,请写一个算法,将该数组中所有值为0的元素都依
可以使用遍历数组的方式,将所有值为0的元素置为倒数第一个非0元素的值。
具体算法如下:
1. 声明一个变量lastNonZeroIdx,用来记录最后一个非0元素的下标。
2. 遍历数组a,对于每个元素a[i]:
- 如果a[i]不为0,将其赋值给变量lastNonZeroIdx,并将lastNonZeroIdx加1。
- 如果a[i]为0,将其替换为a[lastNonZeroIdx]。
3. 遍历完数组后,将lastNonZeroIdx之后的元素都置为0,以保证所有值为0的元素都被移到数组末尾。
算法示例代码如下:
```python
def move_zeros(a):
n = len(a)
lastNonZeroIdx = 0
for i in range(n):
if a[i] != 0:
a[lastNonZeroIdx] = a[i]
lastNonZeroIdx += 1
for i in range(lastNonZeroIdx, n):
a[i] = 0
return a
```
例如,对于数组a=[0, 1, 0, 3, 0, 2],经过move_zeros(a)算法处理后,数组将变为[1, 3, 2, 0, 0, 0]。