首页 > 代码库 > 调整数组顺序使奇数位于偶数前面

调整数组顺序使奇数位于偶数前面

2024-07-30 18:18:42   226人阅读

  • 题目

　　输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)

  • 思路

　　采用两个指针low、high，分别指向数组的头部跟尾部。low指针向后滑动，high指针向前滑动，low指针用来找偶数，high指针用来找基数，然后将两者交换，这类似于快速排序

  • 代码实现

 

public class Algorithm {        /**判断数字num是否为奇数*/    public static boolean isEven(int num){        /**位运算要比%要快*/        if((num & 1) == 1)            return true;        return false;    }        public static void ReorderOddEven(int [] source) {        int low = 0;        int high = source.length - 1;        while(low <= high) {            /**找偶数*/            while(isEven(source[low])) {                ++low;            }            /**找奇数*/            while(!isEven(source[high])) {                --high;            }            if(low <= high) {                /**交换*/                int tmp = source[low];                source[low] = source[high];                source[high] = tmp;            }        }    }        public static void main(String []args) {        int [] array = new int[]{2,4,5,6,3,8,1};        Algorithm.ReorderOddEven(array);        for(int num : array) {            System.out.println(num);        }    }}

 

 

 

　　

调整数组顺序使奇数位于偶数前面


联系
我们