前言:
思虑再三,觉得如果有时间每日一题还是可以更新一下的。
题目难度:基础
解题方法:双指针法
一、题目
输入一个整数数组,
实现一个函数来调整该数组中数字的顺序使得
数组中所有的奇数位于数组的前半部分,所有偶数位于数组的后半部分。
二、题目分析
本题目标:
将给定的整数数组中的奇数和偶数分开,使得奇数在前半部分,偶数在后半部分,同时保持奇数和偶数各自的相对顺序不变。
算法选择:双指针法
选择双指针法是因为它只需要对数组遍历一次即可。时间复杂度较低。
设置两个指针 left 和 right 分别指向数组的头部和尾部。
循环选择:while循环
循环条件是 left < right,这是为了确保两个指针相遇前能够持续进行调整
指针移动的条件及逻辑(奇数在偶数左边)
当left指针指向的数是奇数时,说明当前数字所在位置正确,无需调整,直接移动到下一位(后一位)
当right指针指向的数时偶数时,说明当前数字所在位置正确,无需调整,直接移动到上一位(前一位)
数字交换及位置调整:
当left指向偶数且right指向奇数时,说明这两个数字的位置需要交换。通过交换这两个数字,将奇数移动到数组的前半部分,偶数移动到数组的后半部分。
交换后,left指针后移一位,right 指针前移一位,继续进行下一轮的调整。
三、代码展示:
#include <stdio.h>void sort(int arr[], int sz){ int left = 0; // 指向数组头部的指针 int right = sz - 1; // 指向数组尾部的指针 while (left < right) { if (arr[left] % 2 == 1) { left++; // 如果 left 指向奇数,left 指针后移,因为奇数应在数组前半部分 } else if (arr[right] % 2 == 0) { right--; // 如果 right 指向偶数,right 指针前移,因为偶数应在数组后半部分 } else { int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++; // 交换后 left 指针后移 right--; // 交换后 right 指针前移 } }}int main(){ int arr[10] = { 0 }; int sz = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < sz; i++) { scanf("%d", &arr[i]); // 输入数组元素 } sort(arr, sz); // 调用函数实现奇数在前、偶数在后的调换 for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); // 输出调整后的数组 } return 0;}
结语:
今天这道题比较简单,我写这道题主要也就是想介绍一个双指针法的使用,还望理解!
后面有时间小编会更新一篇文章来详细介绍一下双指针法,敬请期待!