已知顺序表L中的元素为int ,请用C语言写一段时间复杂度为O(n),空间复杂度为O(1)的算法,将L中的奇数元素排在前面,偶数元素排在后面 .
时间: 2023-05-10 17:55:56 浏览: 69
可以使用双指针法,一个指针指向第一个元素,一个指针指向最后一个元素,然后交换奇数和偶数元素的位置,直到两个指针相遇为止。具体实现如下:
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)。
相关问题
已知顺序表l中的元素为int,编写一时间复杂度为o(n)、空间复杂度为o(1)的算法,将l中的奇数元素拓在前面,偶数元素排在后面。
可以使用双指针法,一个指针指向第一个元素,一个指针指向最后一个元素。从前往后扫描,遇到奇数就将其与第一个指针指向的元素交换,第一个指针向后移动一位;遇到偶数就将其与最后一个指针指向的元素交换,最后一个指针向前移动一位。直到两个指针相遇为止,即可完成排序。
时间复杂度为O(n),空间复杂度为O(1)。
已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。
时间复杂度为O(n)、空间复杂度为O(1)的算法,可以采用类似快排的思想,遍历整个线性表,将不等于item的元素移到表头,最后将表的长度减去移动的元素个数即为删除元素后的线性表长度。
具体实现如下:
```c++
void DeleteItem(SeqList &L, int item)
{
int count = 0; // 记录移动元素的个数
for(int i = 0; i < L.length; i++)
{
if(L.data[i] != item)
{
L.data[i - count] = L.data[i];
}
else
{
count++;
}
}
L.length -= count;
}
```
其中,SeqList 是顺序表的结构体,定义如下:
```c++
#define MAX_SIZE 100
typedef struct
{
int data[MAX_SIZE];
int length;
} SeqList;
```
这个算法遍历了整个线性表,时间复杂度为O(n),并且只使用了常数个辅助变量,空间复杂度为O(1)。