【Java 实现经典算法】四:调整数组顺序使奇数位于偶数前面

题目来自剑指Offer之十四。

基本解法

  • 保证奇数和奇数,偶数和偶数之间的相对位置不变
  • 遍历每个元素,一旦发现偶数就取出来,让它之后的元素向前移动,把取出来的元素补到最后的空位上
  • 类似插入排序,具体实现是外循环找奇数,内循环将该数之前的偶数移位
public static void reOrderArray(int array[]){
    
    if(array == null || array.length == 0){
        return;
    }
    
    for(int i = 1; i < array.length; i++){
        int current = array[i];
        if(!isEven(current)){        //找到奇数位置
            int j = i - 1;            //从奇数前一个位置开始
            for(; j >= 0 && isEven(array[j]); j--){    //发现偶数就移位
                array[j + 1] = array[j];
            }
            array[j + 1] = current;        //把奇数插入到偶数前面
        }
    }
}

高效解法

  • 相对位置可以改变时,更为高效的解法
  • 维护两个指针,一首一尾
  • 首指针向后遍历,检测到偶数时暂停,尾指针向前遍历,检测到奇数时暂停
  • 交换首尾两个数
  • 继续这样的判断,直到首尾指针相遇。
public static void reOrderArray2(int array[]){
    
    int low = 0;
    int high = array.length - 1;
    while(low < high){
        while(low < high && !isEven(array[low])){
            low++;
        }
        while(low < high && isEven(array[high])){
            high--;
        }
        if(low < high){
            int temp = array[low];
            array[low] = array[high];
            array[high] = temp;
        }
        
        
    }
    
}

判断一个数是否为偶数

public static boolean isEven(int i){
    return (i & 0x1) == 0;
}

我组建了一个技术交流群,提供免费的每日科技早报服务,里边也会有众多知名互联网企业的技术大佬一起交流学习,共同成长。需要的朋友可以加我微信(微信ID:919201148),我拉你进群,并有福利相送。

【Java 实现经典算法】四:调整数组顺序使奇数位于偶数前面

关注我的微信公众号,回复“礼包”领取我的学习资料

涵盖自学编程、Java技术、分布式笔记、算法刷题和程序员必读电子书等众多资料合集。

【Java 实现经典算法】四:调整数组顺序使奇数位于偶数前面

原文 

https://segmentfault.com/a/1190000022413755

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 【Java 实现经典算法】四:调整数组顺序使奇数位于偶数前面

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址