import java.util.Arrays;
import java.util.Random;
import ljn.help.Helper;
public class OddBeforeEven {
/**
* Q 54 调整数组顺序使奇数位于偶数前面
* 输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
* update at 2012-04-20:
* "quickSort" is O(nlgn).So it does not work
* Now we trade space for time.
* Create another array which has the same length as the array to be sorted.
* Odd number is inserted from front,Even number from tail.
*/
public static void main(String[] args) {
int[] x=new int[10];
for(int i=0;i<10;i++){
x[i]=i;
}
System.out.println(Arrays.toString(x));
sort2(x);
System.out.println(Arrays.toString(x));
System.out.println("================================");
rearrange(x);
System.out.println(Arrays.toString(x));
sort(x);
System.out.println(Arrays.toString(x));
}
//O(n)--Odd number is inserted from front,Even number from tail.
public static void sort(int[] x){
if(x==null||x.length==0){
return;
}
int len=x.length;
int[] tmp=new int[len];
int oddPos=0;
int evenPos=len-1;
for(int i=0;i<len;i++){
if(!isEven(x[i])){
tmp[oddPos++]=x[i];
}else{
tmp[evenPos--]=x[i];
}
}
System.arraycopy(tmp, 0, x, 0, len);
}
//O(nlgn)--like Quick Sort.Find a even from the beginning and a odd from the last.Swap them.
public static void sort2(int[] x){
if(x==null||x.length==0){
return;
}
int len=x.length;
int i=0;
int j=len-1;
while(i<j){
if(!isEven(x[i])){
i++;
continue;
}
if(isEven(x[j])){
j--;
continue;
}
if(isEven(x[i])&&!isEven(x[j])){
Helper.swap(x,i,j);
}
}
}
public static boolean isEven(int x){
return (x&1)==0;
}
/*
20120423 update
1. for i:=1 to n do swap(a[i], a[random(1,n)]); // 凑合,但不是真正随机
2. for i:=1 to n do swap(a[i], a[random(i,n)]); // 真正的随机算法
其中,random(a,b)函数用于返回一个从a到b(包括a和b)的随机整数。
*/
public static void rearrange(int[] x){
int len=x.length;
for(int i=0;i<len;i++){
int j=new Random().nextInt(len);
Helper.swap(x, i, j);
}
}
}
分享到:
相关推荐
title: 剑指Offer-调整数组顺序使奇数位于偶数前面subtitle: 调整数组顺序使奇数位于偶数前面categories: 剑指Offer调整数组顺序
java基础面试题调整数组顺序使奇数位于偶数前面本资源系百度网盘分享地址
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面剑指 Offer 21. 调整数组顺序使奇数位于偶数前面输入一个整数数组,实现一个函数来调整该数组中数字
面试题21. 调整数组顺序使奇数位于偶数前面题目链接面试题21. 调整数组顺序使奇数位于偶数前面题目描述输入一个整数数组,实现一个函数来调整该数组中数字的顺序,
调整数组顺序使奇数位于偶数前面题目描述输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并
今天小编就为大家分享一篇关于Java算法实现调整数组顺序使奇数位于偶数之前的讲解,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
调整数组顺序使奇数位于偶数前面 链表中倒数第 k 个节点 - [移除单链表倒数第 n 个节点] - leetcode 19 反转链表 - [反转单链表] - leetcode 206 合并两个排序的链表 - [合并两个有序链表]- leetcode 21 树的子结构 ...
本篇文章是对数组重排序(如何将所有奇数都放在所有偶数前面)的方法进行了详细的分析介绍,需要的朋友参考下
Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的整数次方调整数组顺序使奇数...
13、调整数组顺序使奇数位于偶数前面 14、链表倒数第k个节点 15、反转链表 16、合并两个排序列表 17、树的子结构 18、二叉树的镜像 19、顺时针打印矩阵 20、包含min函数的栈 21、栈的压入、弹出序列 22、从上到下...
调整数组顺序使奇数位于偶数前面 面试题22 链表中倒数第k个节点 面试题24 反转链表 面试题25 合并两个排序的链表 面试题26 树的子结构 面试题27 二叉树的镜像 面试题28 对称的二叉树 面试题29 顺时针打印矩阵 面试题...
文章目录在其他数都出现偶数次的数组中找到出现奇数次的数整型数组中其他数都出现偶数次找到唯一出现奇数次的数题目算法思路相应代码整型数组中其他数都出现偶数次找到两个出现奇数次的数题目算法思路相应代码 ...
剑指21_调整数组顺序使奇数位于偶数前面_双指针 剑指22_链表的倒数第K的节点_链表_双指针 剑指24_反转链表_链表 剑指25_合并两个有序的链表_链表 剑指27_二叉树的镜像_二叉树 剑指28_对称二叉树_二叉树 剑指29_...
14调整数组顺序使奇数位于偶数前面 15链表中倒数第k个结点 16反转链表 17合并两个排序的链表 18树的子结构 19二叉树的镜像 20顺时针打印矩阵 21包含min函数的栈 22栈的压入弹出序列 23从上往下打印二叉树 24二叉搜索...
调整数组顺序使奇数位于偶数前面 so.19.顺时针打印矩阵 so.28.数组中出现次数超过一半的数字 so.32.把数组排成最小的数 so.35.数组中的逆序对 so.40.数组中只出现一次的数字 so.41.和为S的连续正数序列 so.42.和为S...
调整数组顺序,使奇数位于偶数前面: 链表中倒数第k个节点: 反转链表: 合并两个排序的链表 树的子结构 二叉树的镜像 顺时针打印矩阵 包含main函数的栈 栈的压入、弹出序列 从上往下打印二叉树 二叉搜索树的后序遍历...
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分, 所有偶数位于数组的后半部分。要求时间复杂度为O(n)
打印出杨辉三角形(要求打印出10行如下...有n个整数,使其前面各数顺序向后移m个位置,最后m个数变成最前面的m个数 编写一个函数,输入n为偶数时,调用函数求1/2+1/4+...+1/n,当输入n为奇数时,调用函数1/1+1/3+...+1/n
实例016 用三元运算符判断奇数和偶数 21 实例017 不用乘法运算符实现2×16 22 实例018 实现两个变量的互换 (不借助第3个变量) 23 第4章 流程控制 25 实例019 判断某一年是否为闰年 26 实例020 验证登录信息的合法...
1*9=9 2*9=18 3*9=27 4*9=36 5*9=45 6*9=54 7*9=63 8*9=72 9*9=81 //循环嵌套,打印九九乘法表 public class NineNine{ public static void main(String[]args){ System.out.println(); for (int j=1;j;j++){ ...