今天給大家?guī)淼氖?《劍指 Offer》習(xí)題：調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面存哲，純 Java 實現(xiàn)希望大家多加思考斟叼。
面試題：輸入一個整型數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中的數(shù)字的順序铣猩，使得所有奇數(shù)位于數(shù)組的前半部分股毫，所有偶數(shù)位于數(shù)組的后半部分，希望時間復(fù)雜度盡量小困介。
看到這道題大审，想必大多數(shù)人都是能一下就想到從頭到尾掃描一遍數(shù)組，然后遇到奇數(shù)就移動到最前面座哩，遇到偶數(shù)就移動到最后面的思路徒扶，于是便有了下面的代碼。
注：《劍指 Offer》上面的 「遇到奇數(shù)移動到最前面根穷，遇到偶數(shù)也移動到最后面」其實只需要做其中一種即可姜骡。
public class Test14 {
private static int[] reOrderArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 遇到奇數(shù)就放到最前面
if (Math.abs(arr[i]) % 2 == 1) {
int temp = arr[i];
// 先把 i 前面的都向后移動一個位置
for (int j = i; j > 0; j--) {
arr[j] = arr[j - 1];
}
arr[0] = temp;
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
arr = reOrderArray(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
int[] arr1 = {2, 4, 6, 8, 1, 3, 5, 7, 9};
arr1 = reOrderArray(arr1);
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
int[] arr2 = {2, 4, 6, 8, 10};
arr2 = reOrderArray(arr2);
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}
}
}
上面的代碼固然能達(dá)到功能，但時間復(fù)雜度上完全不能恭維屿良。每找到一個奇數(shù)圈澈，我們總是要去移動不少個位置的數(shù)。
等等尘惧。
我們上面算法最大的問題在于移動康栈，我們能否不做這個移動呢？
當(dāng)然是可以的喷橙。題目要求所有奇數(shù)都應(yīng)該在偶數(shù)前面啥么，所以我們應(yīng)該只需要維護兩個下標(biāo)值，讓一個下標(biāo)值從前往后遍歷重慢，另外一個下標(biāo)值從后往前遍歷饥臂，當(dāng)發(fā)現(xiàn)第一個下標(biāo)值對應(yīng)到偶數(shù)逊躁，第二個下標(biāo)值對應(yīng)到奇數(shù)的時候似踱，我們就直接對調(diào)兩個值。直到第一個下標(biāo)到了第二個下標(biāo)的后面的時候退出循環(huán)稽煤。
我們有了這樣的想法核芽，可以先拿一個例子在心中走一遍，如果沒有問題再寫代碼酵熙，這樣也可以讓面試官知道轧简，我們并不是那種上來就開始寫代碼不考慮全面的程序員。
- 假定輸入的數(shù)組是 {1匾二，2哮独，3拳芙，4，5}皮璧；
- 設(shè)定 odd = 0舟扎，代表第一個下標(biāo)；even = arr.length = 4悴务；
- 從前往后移動第一個下標(biāo) odd睹限，直到它等于偶數(shù)，即當(dāng) odd = 1 的時候讯檐，我們停止移動羡疗；
- 再從后往前移動下標(biāo) even，直到它等于奇數(shù)别洪，即當(dāng) even = 4 的時候叨恨，我們停止移動；
- 滿足 arr[odd] 為偶數(shù)挖垛，arr[even] 為奇數(shù)特碳，我們對調(diào)兩個值，得到新數(shù)組 {1晕换，5午乓，3，4闸准，2}益愈；
- 繼續(xù)循環(huán)，此時 odd = 3,even = 2夷家，不滿足 odd < even 的條件蒸其，退出循環(huán)，得到的數(shù)組符合條件库快；
心中默走一遍沒問題后摸袁，開始手寫代碼：
public class Test14 {
private static int[] reOrderArray(int[] arr) {
int odd = 0, even = arr.length - 1;
// 循環(huán)結(jié)束條件為 odd >= even
while (odd < even) {
// 第一個下標(biāo)為偶數(shù)的時候停止
while (odd < even && Math.abs(arr[odd]) % 2 != 0) {
odd++;
}
// 第二個下標(biāo)為奇數(shù)的時候停止
while (odd < even && Math.abs(arr[even]) % 2 == 0) {
even--;
}
// 找到后對調(diào)兩個值
int temp = arr[odd];
arr[odd] = arr[even];
arr[even] = temp;
}
return arr;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
arr = reOrderArray(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
int[] arr1 = {2, 4, 6, 8, 1, 3, 5, 7, 9};
arr1 = reOrderArray(arr1);
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
int[] arr2 = {2, 4, 6, 8, 10};
arr2 = reOrderArray(arr2);
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println();
}
}
擴展性更好的代碼，能秒殺 Offer
如果是面試應(yīng)屆畢業(yè)生或者工作時間不長的程序員义屏，面試官可能會滿意前面的代碼靠汁，但如果應(yīng)聘者申請的是資深 的開發(fā)崗位，那面試官可能會接著問幾個問題闽铐。
- 面試官：如果把題目改成把數(shù)組中的數(shù)組按照大小分為兩部分蝶怔，所有的負(fù)數(shù)都在非負(fù)整數(shù)的前面，該怎么做兄墅？
- 應(yīng)聘者：這很簡單踢星，可以重新定義一個函數(shù)，在新的函數(shù)里隙咸，只要修改第二個和第三個 while 循環(huán)里面的判斷條件就好了沐悦。
- 面試官：如果再把題目改改成洗，變成把數(shù)組中的數(shù)分為兩部分，能被 3 整除的數(shù)都在不能被 3 整除的數(shù)的前面藏否，怎么辦泌枪？
- 應(yīng)聘者：我們還是可以定義一個新的函數(shù)，在這個函數(shù)中......
- 面試官：(打斷應(yīng)聘者的話)秕岛，難道就沒有更好的方法碌燕？
這個時候應(yīng)聘者應(yīng)該要反應(yīng)過來，面試官期待我們能提供的不僅僅是解決一個問題的辦法继薛，而是解決一系列同類型問題的通用方法修壕。我們在做解法的時候不能只想著解決當(dāng)前的問題就好。在《大話設(shè)計模式》中遏考，講解了一個非常有意思的事情就是大鳥讓小菜做商場促銷活動的時候慈鸠，各種改變需求，把小菜繞的云里霧里灌具。
《大話設(shè)計模式》PDF 版本可以在公眾號后臺回復(fù)「大話設(shè)計模式」即可獲取青团。
是呀，哪有不變的需求咖楣，需求不變督笆，我們哪來那么多活干呀？不過要是诱贿，我們事先就做了這樣的準(zhǔn)備娃肿，省下來的時間那不是正好又可以去玩一盤吃雞洛？
回到面試官新提出的兩個問題來珠十，我們其實新的函數(shù)都只需要更改第二個和第三個 while 循環(huán)里面的判斷條件料扰，而其它都是不需要動的。
public class Test14 {
interface ICheck {
boolean function(int n);
}
public static class OrderEven implements ICheck {
@Override
public boolean function(int n) {
return n % 2 == 0;
}
}
private static int[] reOrderArray(int[] arr, ICheck iCheck) {
int odd = 0, even = arr.length - 1;
// 循環(huán)結(jié)束條件為 odd >= even
while (odd < even) {
// 第一個下標(biāo)為偶數(shù)的時候停止
while (odd < even && !iCheck.function(arr[odd])) {
odd++;
}
// 第二個下標(biāo)為奇數(shù)的時候停止
while (odd < even && iCheck.function(arr[even])) {
even--;
}
// 找到后對調(diào)兩個值
int temp = arr[odd];
arr[odd] = arr[even];
arr[even] = temp;
}
return arr;
}
public static void main(String[] args) {
OrderEven even = new OrderEven();
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
arr = reOrderArray(arr,even);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
int[] arr1 = {2, 4, 6, 8, 1, 3, 5, 7, 9};
arr1 = reOrderArray(arr1,even);
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
int[] arr2 = {2, 4, 6, 8, 10};
arr2 = reOrderArray(arr2,even);
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println();
}
}
寫這玩意兒的時候焙蹭，我內(nèi)心是拒絕的晒杈，由于 Java 沒有 Python 一樣方便的函數(shù)指針，我想了想只想到了用接口方式來處理孔厉。要是有其他實現(xiàn)方式的希望大家能在評論區(qū)留言~
好了拯钻，今天的面試講解，就先到這兒吧烟馅。
