酷播亮新聞
文章摘要： 調整陣列中元素順序 題目解題思路 陣列中有一個元素出現的次數超過陣列長度的一半
打個比方，在金庸的武俠世界裏，數據結構和演算法它就像一門上乘的內功心法，一旦掌握了它，各種武功信手拈來（張無忌就是典型的例子）； 對於程式設計師來說，它能決定你在技術這條道路上能走多遠。 現在去大公司面試，都會有演算法題。本文主要涉及陣列、字串、List這幾個數據結構，我們一起來分析和解答幾道常見演算法題，後面我會分享一下我的學習心得和一些解題套路。
題目1：翻轉句子
題目： 給定一個英文句子，每個單詞之間都是由一個或多個空格隔開，請翻轉句子中的單詞順序（包括空格的順序），但單詞內字元的順序保持不變。例如輸入」www google com 「，則應輸出」 com google www」。
如果你經常關注演算法相關文章，這道題應該會比較熟悉，各種部落格和書籍上都有出現，不熟悉也沒關係，現在我們就一起來嘗試解答下。要注意一下和網上流傳的題目的不同點：每個單詞之間都是由 一個或多個空格隔開 ，而網上大多是單詞間由空格分隔， 有且只有一個空格。
解題思路
試想一下，如果將整個字串翻轉，結果是句子是反轉了，但單詞內的字元順序也翻轉了。如果要保證單詞內順序不變，只需要再將每個單詞翻轉一下就滿足要求了。
理一下思路：
- 第一步翻轉所有字元。比如翻轉」www google com 「中所有的字元得到」 moc elgoog www」，可以看出不僅翻轉了句子中單詞的順序，連單詞內的字元順序也翻轉了。
- 第二步再翻轉每個單詞中字元的順序，就得到了」 com google www」。這正是符合題目的輸出。
此思路的關鍵是： 1. 實現一個函式/方法，翻轉字串中的一段。 2. 判斷句子中的單詞，注意空格。
測試用例
- 功能測試：多個單詞、1個單詞、單詞間只有一個空格、單詞間有多個空格。
- 特殊輸入測試：空字元、字串中只有空格、null物件（指標）。
編碼實現
/**
* @param chars 原字串
* @param start 大於等於0
* @param end 小於 length
* @return
*/
private char[] v1_0_reverse(char[] chars, int start, int end) {
// str 判斷null， 索引有效值判斷
if (chars == null || start < 0 || end >= chars.length || start >= end) {
return chars;
}
while (start < end) {
// 收尾字元互換，直到替換完成。
char temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
start++;
end--;
}
return chars;
}
private String v1_0_solution(String sentence) {
if (sentence == null || sentence.isEmpty()) {
return sentence;
}
int length = sentence.length();
// 第一步翻轉所有字元
char[] chars = v1_0_reverse(sentence.toCharArray(), 0, length - 1);
System.out.println(new String(chars));
// 第二步翻轉每個單詞（重點：怎麼找到單詞）
int start = 0, end = 0;
while (start < length) {
if (chars[start] == ' ') {
// 遇到空格就向右邊繼續查詢
start++;
end++;
} else if (end == length || chars[end] == ' ') {
// 遇到空格或者已經到了字串末尾，此時翻轉找到的單詞內部字元，這裏需要注意end-1
chars = v1_0_reverse(chars, start, end - 1);
System.out.println(new String(chars));
// 重新制定檢查索引start
start = end++;
} else {
// end加1，爲了檢查單詞是否結束
end++;
}
}
return new String(chars);
}
// 反轉字串
void Reverse(char *pBegin, char *pEnd)
{
if(pBegin == NULL || pEnd == NULL)
return;
while(pBegin < pEnd)
{
char temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
pBegin ++, pEnd --;
}
}
// 翻轉句子中單詞順序，但保證單詞內字元順序不變。
char* ReverseSentence(char *pData)
{
if(pData == NULL)
return NULL;
char *pBegin = pData;
char *pEnd = pData;
while(*pEnd != ' ')
pEnd ++;
pEnd--;
// 翻轉整個句子
Reverse(pBegin, pEnd);
// 翻轉句子中的每個單詞
pBegin = pEnd = pData;
while(*pBegin != ' ')
{
if(*pBegin == ' ')
{
pBegin ++;
pEnd ++;
}
else if(*pEnd == ' ' || *pEnd == ' ')
{
Reverse(pBegin, --pEnd);
pBegin = ++pEnd;
}
else
{
pEnd ++;
}
}
return pData;
}
如果你在面試的時候遇到這道題，並且很容易就想到了這個演算法，有經驗的面試官就會在這道題基礎上加點難度，繼續考查面試者。so，第二道題來了：
題目：接上題，面試官繼續提問，我們得到的」 com google www」需要被用作一個URL的引數，所以這裏需要的處理是去掉開頭結尾的無效空格，並將兩個單詞中間的每一個空格都替換為」%20」。例如」 com google www」應被轉換為」com%20%20google%20www」，請給出轉換函式。
解題思路
- 第一步去掉收尾的無效空格；比如」 com google www」去掉後得到」com google www」。
- 第二步將兩個單詞中間的每一個空格都替換為」%20」。
測試用例
- 功能測試：前後有無空格情況、中間一個或多個空格情況。
- 特殊輸入測試：空字元、字串中只有空格、null物件（指標）。
編碼實現
private String v1_1_solution(String sentence) {
if (sentence == null || sentence.isEmpty()) {
return sentence;
}
// 去掉字串收尾的空格
sentence = trim(sentence);
int len = sentence.length();
char[] chars = sentence.toCharArray();
int count = getSpaceCount(sentence);
int newLen = 2 * count + len;
// 擴容，內部使用System.arraycopy 方法實現。
chars = Arrays.copyOf(chars, newLen);
int index = len - 1;
int newIndex = newLen - 1;
while (index >= 0 && newIndex > index) {
if (chars[index] == ' ') {
chars[newIndex--] = '0';
chars[newIndex--] = '2';
chars[newIndex--] = '%';
} else {
chars[newIndex--] = chars[index];
}
index--;
}
return new String(chars);
}
/**
* 剔除字串收尾的空格
*
* @param origin
* @return
*/
private String trim(String origin) {
char[] chars = origin.toCharArray();
int length = chars.length;
int st = 0;
while (st < length && chars[st] == ' ') {
st++;
}
while (st < length && chars[length - 1] == ' ') {
length--;
}
// 如果收尾有空格，就擷取生成新的字串
if (st > 0 || length < chars.length) {
origin = new String(chars, st, (length - st));
}
return origin;
}
private int getSpaceCount(String sentence) {
char[] chars = sentence.toCharArray();
int count = 0;
for (char c : chars) {
if (c == ' ') {
count++;
}
}
return count;
}
// todo
題目2：調整陣列中元素順序
題目： 給定一個整數陣列，請實現一個函式來調整陣列中數字的順序，使得所有奇數都位於偶數之前。
解題思路
此題比較簡單，我最先想到的解法是這樣：我們維護兩個指標(索引)，一個指標指向陣列的第一個數字，稱之為頭指標，向右移動；一個指標指向最後一個數字，稱之為尾指標，向左移動。
這樣，兩個指標分別從陣列的頭部和尾部向陣列的中間移動，如果第一個指標指向的數字是偶數而第二個指標指向的數字是奇數，我們就交換這兩個數字。
迴圈結束條件：兩個指標重疊時，已完成排序，此時退出迴圈。
可以看出此演算法，一次迴圈搞定，所以時間複雜度O(n), 由於在原陣列上操作，所以空間複雜度O(1)。
測試用例
- 功能測試：全是奇數、全是偶數、奇偶數存在但已排好序/未排好序。
- 特殊輸入測試： null物件、陣列元素為0、有負數情況。
編碼
private int[] v2_0_solution(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int st = 0;
int end = nums.length - 1;
while (st < end) {
// find even number
if (isOdd(nums[st])) {
st++;// 奇數，索引右移
} else if (!isOdd(nums[end])) {
end--;// 偶數，索引左移
} else {
// 奇偶數互換
int temp = nums[st];
nums[st] = nums[end];
nums[end] = temp;
st++;
end--;
}
}
return nums;
}
// 與1做按位運算，不為0就是奇數，反之為偶數
private boolean isOdd(int n) {
return (n & 1) != 0;
}
//判斷是否為奇數
bool IsOdd(int data)
{
return data & 1 != 0;
}
//奇偶互換
void OddEvenSort(int *pData, unsigned int length)
{
if (pData == NULL || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;
while (pBegin < pEnd)
{
//如果pBegin指標指向的是奇數，正常，向右移
if (IsOdd(*pBegin))
{
pBegin++;
}
//如果pEnd指標指向的是偶數，正常，向左移
else if (!IsOdd(*pEnd))
{
pEnd--;
}
else
{
//否則都不正常，交換
//swap是STL庫函式，宣告為void swap(int& a, int& b);
swap(*pBegin, *pEnd);
}
}
}
有經驗的面試官又來了，題目難度需要升下級，:no_mouth:~
題目： 接上題，面試官會繼續要求改造此函式使其能夠保證原先輸入陣列的奇數內部順序以及偶數內部順序，即如果輸入為{2，1，3，6，4，7，8，5}，則輸出應為{1，3，7，5，2，6，4，8}，奇數之間的相互順序和偶數之間的相互順序不得被改變。
解題思路
要想保證原陣列內元素的順序，可使用O(n)的temp陣列空間按順序快取偶數，奇數依次放到原陣列前面，最後將temp中偶數取出放在原陣列後面。
來畫圖理解下~
測試用例
同上一題。這裏就省略了。
編碼
private int[] v2_1_solution(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int st = 0;
int evenCount = 0;
// 申請的記憶體空間temp
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (!isOdd(nums[i])) {
evenCount += 1;
temp[evenCount - 1] = nums[i];
} else {
if (st < i) {
// 將奇數依次放在原陣列前面
nums[st] = nums[i];
}
st++;
}
}
// 將temp中偶數取出放在原陣列後面
if (evenCount > 0) {
for (int i = st; i < nums.length; i++) {
nums[i] = temp[i - st];
}
}
return nums;
}
// todo
題目3：利用陣列實現一個簡易版的List
題目：請利用陣列實現一個簡易版的List，需要實現poll和push兩個介面，前者為移除並獲得隊頭元素，後者為向隊尾新增一個元素，並要求能夠自動擴容。
解題思路
此題關鍵是在怎麼實現poll和push兩個介面上。
- poll（獲取並移動對頭元素）：移動陣列並置空最後一個元素。
- push（新增元素）：按索引新增到陣列中，size大於陣列長度就先擴容。
測試用例
- 功能測試： 新增、移除元素
- 特殊測試： 新增大量資料（測試擴容）、移除所有元素、null資料
編碼
private static final int DEFAULT_CAPACITY = 16;
private Object[] elementData;
// 實際儲存的元素數量
// The size of the List (the number of elements it contains).
private int size;
public CustomList() {
elementData = new Object[DEFAULT_CAPACITY];
}
public CustomList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = new Object[DEFAULT_CAPACITY];
} else {
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
/**
* 移除並獲得隊頭元素
*
* @return
*/
public Object poll() {
if (size <= 0){
throw new IndexOutOfBoundsException(" list is empty .");
}
// 獲取隊頭第一個元素
Object oldValue = elementData[0];
// 陣列元素左移一位 & 最後一位元素置空
System.arraycopy(elementData, 1, elementData, 0, size - 1);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 向隊尾新增一個元素
*
* @param item
*/
public void push(Object item) {
ensureExplicitCapacity(size + 1); // Increments modCount!!
elementData[size++] = item;
}
@Override
public String toString() {
return Arrays.toString(elementData);
}
// 這裏擴容參考的ArrayList，具體實現請點選文末原始碼連結前往檢視。
private void ensureExplicitCapacity(int minCapacity) {
// 期望的最小容量大於現有陣列的長度，則進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// todo
題目4：陣列中出現次數超過一半的數
題目： 一個整數陣列中有一個數字出現的次數超過了陣列長度的一半，請找出這個數字。如輸入一個長度為9的陣列{1，2，3，2，2，2，5，4，2}，由於2出現了5次，超過了陣列長度的一半，因此應輸出2。
解題思路
如果我們將陣列排序，那麼排序後位於陣列中間的的數字一定是那個出現次數超過陣列長度一半的數字。
測試用例
- 存在（或者不存在）次數超過陣列長度一半的數。
- 特殊用例： null、空元素、 只有一個數。
編碼
- Java實現
// todo
todo
有經驗的面試官又來了，題目難度需要升下級，:no_mouth:~
題目：這個題目有很多變種，其中一個引申為輸入的是一個物件陣列，該物件無法比較大小，只能利用equals()方法比較是否相等，此時該如何解（若要用到O(n)的輔助空間，能否避免？）。
解題思路
陣列中有一個元素出現的次數超過陣列長度的一半， 也就是說它出現的次數比其他所有元素出現次數的和還要多。
因此我們可以考慮在遍歷陣列的時候儲存兩個值： 一個是陣列中的一個元素， 一個是次數。當我們遍歷到下一個元素的時候，如果下一個原色和我們之前儲存的元素相等（equals返回true），則次數加1；如果下一個元素和我們之前儲存的不相等，則次數減1。如果次數為0，我們需要儲存下一個元素，並把次數設為1。由於我們要找的數字出現的次數比其他所有數字出現的次數之和還要多，那麼要找的數字肯定是最後一次把次數設為1時對應的那個元素。
此思路：空間複雜度O(1),時間複雜度O(n)。
編碼
private Object v4_1_solution(Object[] objects) {
if (objects == null || objects.length < 1) {
throw new IllegalArgumentException(" array is empty. ");
}
// 假設第一個元素就是超過長度一半的那個
Object result = objects[0];
int times = 1;
// 從第二個元素開始遍歷
for (int i = 1; i < objects.length; i++) {
if (times == 0) {
// 重新設定
result = objects[i];
times = 1;
} else if (objects[i].equals(result)) {
times++;
} else {
times--;
}
}
if (checkMoreThanHalf(objects, result)) {
return result;
} else {
throw new IllegalArgumentException(" array is invalid ");
}
}
private boolean checkMoreThanHalf(Object[] objects, Object obj) {
int times = 0;
for (int i = 0; i < objects.length; i++) {
if (objects[i].equals(obj)) {
times++;
}
}
return times * 2 > objects.length;
}
// 測試類，重點在於實現了equals和hashcode方法。
private static class TestObject {
String unique;
public TestObject(String unique) {
this.unique = unique;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
TestObject that = (TestObject) o;
return unique != null ? unique.equals(that.unique) : that.unique == null;
}
@Override
public int hashCode() {
return unique != null ? unique.hashCode() : 0;
}
@Override
public String toString() {
return "TestObject{" +
"unique='" + unique + ''' +
'}';
}
}
todo
學習心得&解題套路
細心的讀者可能發現了，文中解題過程大致是這樣的：分析思路->測試用例->編碼->除錯並通過測試。
總結
你可能會問怎樣才能很好的掌握演算法程式設計呢？我的答案是： 有事沒事刷道題吧。勤加練習，終成大神。 文中所有程式碼均編譯執行並通過測試用例檢查。程式碼獲取請前往： https://github.com/yangjiantao/DSAA 。 由於作者水平有限，文中錯誤之處在所難免，敬請讀者指正。
程式設計能力就像任何其他技能一樣，也是一個可以通過刻意練習大大提高的。 — 摘抄至LeetCode。