##題目描述 輸入一個整數陣列，實作一個函式來調整該陣列中數字的順序，使得所有的奇數位于陣列的前半部分，所有的偶數位于陣列的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變，
思路
空間換時間，佇列，時間復雜度O(n)，空間復雜度O(n)，
穩定原地排序，冒泡，時間復雜度O(n2)，空間復雜度O(1)，
空間換時間代碼
import java.util.*;
public class Solution {
public void reOrderArray(int [] array) {
Queue<Integer> queue1 = new LinkedList<Integer>();
Queue<Integer> queue2 = new LinkedList<Integer>();
for(int a : array) {
if(a%2 == 1){
queue1.offer(a);
} else {
queue2.offer(a);
}
}
for(int i = 0; i < array.length; i++) {
if(queue1.peek() != null) {
array[i] = queue1.poll();
} else {
array[i] = queue2.poll();
}
}
}
}
冒泡排序
import java.util.*;
public class Solution {
public void reOrderArray(int [] array) {
int oddcount = 0;
for(int a : array) {
if(a%2 == 1) {
oddcount++;
}
}
for(int i = 0; i < oddcount; i++) {
// 無交換則退出
boolean flag = true;
for(int j = array.length - 1; j > i; j--) {
if(array[j]%2 == 1 && array[j-1]%2 == 0){
int tmp = array[j];
array[j] = array[j-1];
array[j-1] = tmp;
flag = false;
}
}
if(flag){
break;
}
}
}
}
筆記
-
offer，add 區別：
一些佇列有大小限制，因此如果想在一個滿的佇列中加入一個新項，多出的項就會被拒絕，
這時新的 offer 方法就可以起作用了，它不是對呼叫 add() 方法拋出一個 unchecked 例外，而只是得到由 offer() 回傳的 false， -
poll，remove 區別：
remove() 和 poll() 方法都是從佇列中洗掉第一個元素，remove() 的行為與 Collection 介面的版本相似， 但是新的 poll() 方法在用空集合呼叫時不是拋出例外，只是回傳 null，因此新的方法更適合容易出現例外條件的情況， -
peek，element區別：
element() 和 peek() 用于在佇列的頭部查詢元素，與 remove() 方法類似，在佇列為空時， element() 拋出一個例外，而 peek() 回傳 null，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86926.html
標籤：其他
下一篇：鏈表中倒數第k個結點