数据结构|设计一个算法，将顺序表的所有奇数移动到偶数的前面
·
题目：
设计一个算法，将顺序表的所有奇数移动到偶数的前面
思路：
法1：可以从头扫描顺序表的元素，当扫描到该元素为奇数，让k++，奇数区间+1（k初始值为-1），然后让该元素与L->data[i]交换
代码：
void MoveNum(seqlist*& L) {
//法一：
int i = 0,k=-1;
for (i = 0; i < L->length; i++) {
if (L->data[i] % 2 == 1) {
//是奇数,增加奇数区间
k++;
//不是在同一个位置，则交换
if (i != k) {
swap(L->data[i], L->data[k]);
}
}
}
}
思路：
法2：可以从两端开始扫描，如果左边扫描的元素为奇数，则跳过，如果右边扫描的元素为偶数，则跳过，直到左边找到偶数，右边找到奇数，让这两个数交换
void MoveNum(seqlist*& L) {
//法2
int i = 0,j = L->length - 1;
while (i<j)
{
while (i < j && L->data[i] % 2 == 1) {
i++;
}
while (i<j&&L->data[j]%2==0)
{
j--;
}
if (i < j) {
swap(L->data[i], L->data[j]);
}
}
}
这两种方法的时间复杂度都是O(n),空间复杂度是O(1)，属于高效算法
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
5
0- 0
已为社区贡献9条内容
所有评论(0)