写在前面:
为了增长一下自己的数据结构能力,也为了面试准备,准备将剑指Offer做一下,并与各位分享,希望各位可以对代码以及思路提提建议,欢迎志同道合者,谢谢。
题目:
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
思路:
原数组 4,2,5,7,8,1 变成 5,7,1,4,2,8
类似于直接插入的方式,从第二个数据开始判断,如果是奇数就查询前面的一个数据,判断是奇数还是偶数,如果是偶数,将这个数插入前面一个数,如果前面一个数是奇数,就不动,最核心的是,只要是找到了奇数,那么就向前找,直到找到前面的奇数,然后把这个数放在前面奇数的后面。如果找到了第一个还不是奇数,那么就把这个奇数放在第一位,
代码实现
package com.itzmn.offer;
/**
* @Auther: 张梦楠
* @Date: 2018/7/30 09:39
* 简书://www.greatytc.com/u/d611be10d1a6
* 码云:https://gitee.com/zhangqiye
* @Description:
*
* 2,4,6,1,3,5,7
* 2 1 3 5 7 4 6
*
* 使用类似直接插入方法, 将负数直接插入到前面的有序队列
*
*/
public class Offer13 {
public static void main(String[] args) {
int[] array = {2,4,6,1,3,5,7};
new Offer13().reOrderArray(array);
for (int i:array){
System.out.println(i);
}
}
public void reOrderArray(int [] array) {
for (int i=1;i<array.length;i++){
if (array[i] % 2 == 1){
int temp = array[i];
for (int j=i-1;j>=0;j--){
if (array[j] % 2 == 0){
array[j+1] = array[j];
}
if (array[j] % 2 == 1){
array[j+1] = temp;
break;
}
if (j == 0){
array[0] = temp;
}
}
}
}
}
}
希望大家可以多多指点,优化一下,
QQ群:552113611