/*【问题描述】请调整顺序表的数据,使得左边为奇数,右边为偶数,要求时间复杂度为O(n)。 【样例输入】25 34 57 50 16 48 9 62 0 【样例输出】25 9 57 50 16 48 34 62 【注意】0代表输入的结束,由于调整思路的
时间: 2023-06-15 11:07:22 浏览: 72
原因,不需要将0移动到左边或右边。*/
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void adjust(int arr[], int len) {
int left = 0, right = len - 1;
while (left < right) {
while (arr[left] % 2 == 1 && left < right) left++; // 找到左边第一个偶数
while (arr[right] % 2 == 0 && left < right) right--; // 找到右边第一个奇数
swap(&arr[left], &arr[right]); // 交换
}
}
int main() {
int arr[100], len = 0, num;
while (scanf("%d", &num) != EOF) {
if (num == 0) break;
arr[len++] = num;
}
adjust(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
相关问题
已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分,左边的元素(即排在前面的)均为奇数,右边所有元素(即排在后面的)均为偶数,并要求算法的时间复杂度为O(n),空间复杂度为O(1)。
算法分析:
- 定义两个指针i和j,分别指向序列的第一个元素和最后一个元素;
- i向右移动,直到指向一个偶数;
- j向左移动,直到指向一个奇数;
- 如果i<j,则交换i和j指向的元素,并继续执行步骤2、3、4;
- 如果i>=j,则调整完成。
算法实现:
void adjustList(int L[], int len) {
int i = 0, j = len - 1;
while (i < j) {
while (i < j && L[i] % 2 != 0) {
i++;
}
while (i < j && L[j] % 2 == 0) {
j--;
}
if (i < j) {
int temp = L[i];
L[i] = L[j];
L[j] = temp;
}
}
}
时间复杂度为O(n),空间复杂度为O(1)。
已知顺序表L中的元素为int ,请用C语言写一段时间复杂度为O(n),空间复杂度为O(1)的算法,将L中的奇数元素排在前面,偶数元素排在后面 .
可以使用双指针法,一个指针指向第一个元素,一个指针指向最后一个元素,然后交换奇数和偶数元素的位置,直到两个指针相遇为止。具体实现如下:
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void odd_even_sort(int *L, int n) {
int i = 0, j = n - 1;
while (i < j) {
while (i < j && L[i] % 2 == 1) i++;
while (i < j && L[j] % 2 == 0) j--;
if (i < j) swap(&L[i], &L[j]);
}
}
时间复杂度为O(n),空间复杂度为O(1)。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)