剑指Offer - 面试题21:调整数组顺序使奇数位于偶数前面

简介: 剑指Offer - 面试题21:调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。


分析

暴力法

最简单能想到的就是从前到后依次遍历若发现是偶数,先保存当前元素,将后面全部往前移动,然后把保存的元素给到最后那个位置。时间复杂度为O(n2),空间复杂度为O(1);


C

#include<stdio.h>
#include<assert.h>
//暴力法
void ReordeOddEven(int* pData, unsigned int length)
{
    assert(NULL != pData);
    assert(length > 0);
    int i = 0;
    int j = 0;
    for(i = 0; i < length; i++)
    {
        if((pData[i] & 1) == 0)//&优先级低于==所以务必加括号,否则永远不成立
        {    
            int tmp = pData[i];
            for(j = i; j < length - 1; j++)
            {
                pData[j] = pData[j + 1];
            }
            pData[j] = tmp;
        }
    }
}
void Print(int* n, int length)
{
    int i = 0;
    for(i = 0; i < length; i++)
    {
        printf("%d ", n[i]);
    }
    printf("\n");
}
int main()
{
    int n[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int length = sizeof(n) / sizeof(n[0]);
    ReordeOddEven(n, length);
    Print(n, length);
    return 0;
}


双指针

我们还可以用俩个指针。分别指向头和尾巴。


让start指针向后走找偶数,让end指针向前走找奇数。循环条件:start<end

C

#include<stdio.h>
#include<assert.h>
void swap(int* n , int i, int j)
{
    int tmp = n[i];
    n[i] = n[j];
    n[j] = tmp;
}
void ReordeOddEven(int* pData, unsigned int length)
{
    assert(NULL != pData);
    assert(length > 0);
    int start = 0;
    int end = length - 1;
    while(start < end)
    {
        while(start < end && (pData[start] & 1) == 1)//如果是奇数就一直找
        {
            start++;
        }
        while(start < end && (pData[end] & 1) == 0)//如果是偶数就一直找
        {
            end--;
        }
        if(start < end)
        {
            swap(pData, start, end);
        }
    }
}
void Print(int* n, int length)
{
    int i = 0;
    for(i = 0; i < length; i++)
    {
        printf("%d ", n[i]);
    }
    printf("\n");
}
int main()
{
    int n[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int length = sizeof(n) / sizeof(n[0]);
    ReordeOddEven(n, length);
    Print(n, length);
    return 0;
}

具有扩展性的双指针


分析上面代码我们发现核心就只有俩段代码(pData[start] & 1)(pData[end] & 1),我们把这个代码封装成一个函数,这个地方直接调用封装好的函数就ok了。

C

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
bool func(int n)
{
    return (n & 1) == 0;
}
void swap(int* n, int i, int j)
{
    int tmp = n[i];
    n[i] = n[j];
    n[j] = tmp;
}
void ReordeOddEven(int* pData, unsigned int length)
{
    assert(NULL != pData);
    assert(length > 0);
    int start = 0;
    int end = length -1;
    while(start < end)
    {
        while(start < end && func(pData[start])  == false)
        {
            start++;
        }
        while(start < end && func(pData[end]) == true)
        {
            end--;
        }
        if(start < end)
        {
            swap(pData, start, end);
        }
    }
}
void Print(int* n, int length)
{
    int i = 0;
    for(i = 0; i < length; i++)
    {
        printf("%d ", n[i]);
    }
    printf("\n");
}
int main()
{
    int n[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int length = sizeof(n) / sizeof(n[0]);
    ReordeOddEven(n, length);
    Print(n, length);
    return 0;
}


本章完!

目录
相关文章
|
9天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
22天前
|
开发框架 .NET
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
|
1月前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
14天前
|
存储 算法 Java
Java面试之SpringCloud篇
Java面试之SpringCloud篇
30 1
|
14天前
|
缓存 NoSQL Redis
Java面试之redis篇
Java面试之redis篇
34 0
|
14天前
|
SQL 关系型数据库 MySQL
java面试之MySQL数据库篇
java面试之MySQL数据库篇
22 0
java面试之MySQL数据库篇