數(shù)組系列的第二篇文章永品。
- 調整數(shù)組順序，使奇數(shù)位于偶數(shù)前面
- 順時針打印矩陣
- 查找數(shù)組中出現(xiàn)次數(shù)大于一半的數(shù)字
1.調整數(shù)組順序击纬，使奇數(shù)位于偶數(shù)前面
問題描述：輸入一個整數(shù)上數(shù)組鼎姐，實現(xiàn)一個函數(shù)來調整該數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，偶數(shù)位于后半部分炕桨。
算法思想
思路一：遍歷數(shù)組饭尝，每遇到一個偶數(shù)，就將這個數(shù)字后面的所有數(shù)字向前移動一位献宫，然后把這個數(shù)字放到數(shù)組末尾钥平，這樣每遇到一個偶數(shù)，就需要進行O(n)次移動姊途，所以整個算法的時間復雜度為O(n^2).
思路二：既然是把數(shù)組中的技術和偶數(shù)分開涉瘾，奇數(shù)在前，偶數(shù)在后捷兰，我們可以嘗試使用兩個指針立叛，第一個指針指向開頭，第二個指針指向結尾贡茅，
1.判斷前一個指針指向的是否是奇數(shù) 秘蛇，如果是，則指針后移顶考，直到遇到下一個偶數(shù)為止赁还，否則和后一個指針(指向奇數(shù))交換元素位置；
2.判斷后一個指針指向的是否是奇數(shù)村怪，如果是奇數(shù)秽浇，就和前一個指針指向的偶數(shù)交換位置浮庐，否則就指針前移甚负，直到遇到下一個奇數(shù)。
代碼
注意：代碼中需要注意的地方是病涨，在移動指針時，一直對pBegin,pEnd大小的判斷璧坟，一旦pEnd>=pBegin既穆，就可以結束循環(huán)了。
void ReorderOddEven0 (int *pData, unsigned int length)
{
if (pData == NULL || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;//指向數(shù)組最后一個元素
while (pBegin < pEnd)
{
//如果前一個指針指向的是奇數(shù)雀鹃，就一直往后移
while (pBegin < pEnd && (*pBegin % 2) == 1)
pBegin++;
//向前移動指針幻工，直到指向奇數(shù)
while (pBegin < pEnd && (*pEnd % 2) == 0)
pEnd--;
if (pBegin < pEnd)
{
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
}
這樣一道題解決了，那如果遇到要分離正數(shù)和負數(shù)的題呢黎茎？要將能被3整除的數(shù)排在數(shù)組前面囊颅，不能被3整除的排后面呢？是不是修改內層的兩個while循環(huán)的條件就可以了。其實還有更好的辦法踢代。
思路三：將思路二的代碼拆分開盲憎，用于解決這類的一系列問題，比如說將負數(shù)移動前面胳挎，將能被3整除的移到前面等饼疙。這些問題的解決方法沒有多大的差異，唯一的差異就是在移動指針時的判斷慕爬，我們可以使用一個函數(shù)宏多，用于判斷指針知否該移動，而原來的函數(shù)就負責移動指針澡罚。
代碼
思路二的改進伸但，更具可擴展性。
在下面的代碼中留搔，將判斷是否移動指針的代碼封裝成一個函數(shù)更胖，作為參數(shù)傳入，降低和代碼的耦合性隔显，現(xiàn)在却妨，這一類問題，我們都只需修改func函數(shù)就可以了括眠。
//將移動指針和判斷是否該移動分開
void Reorder(int *pData, unsigned int length, bool (*func) (int))
{
if (pData == NULL || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;//指向數(shù)組最后一個元素
while (pBegin < pEnd)
{
//如果前一個指針指向的是奇數(shù)彪标，就一直往后移
while (pBegin < pEnd && !func(*pBegin))
pBegin++;
//向前移動指針，直到指向奇數(shù)
while (pBegin < pEnd && func(*pEnd))
pEnd--;
if (pBegin < pEnd)
{
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
}
bool isEven(int num)
{
return (num % 2) == 0;
}
void ReorderOddEven1(int *pData, unsigned int length)
{
Reorder(pData, length, isEven);
}
2.順時針打印矩陣
問題描述：輸入一個矩陣掷豺，按照從外到內捞烟，順時針順序一次打印出每一個數(shù)字。
算法思想
這一題沒有涉及到復雜的數(shù)據(jù)結構或者高級的算法当船，但是我們能想到代碼應該會有很多循環(huán)题画，所以邊界條件更為重要。既然是順時針打印矩陣德频，我們可以把它想象成在矩陣上有若干個圈苍息，每次用一個循環(huán)打印一圈之內的元素。現(xiàn)在我們考慮邊界條件壹置。
先看5*5的矩陣竞思，最外層圈左上角的坐標是(0,0),下一層左上角的坐標是(1,1),最內層只有1個元素，左上角坐標為(2,2)钞护。再看6*6的矩陣盖喷，最內層是4個元素，左上角的坐標也是(2,2)患亿。假設每個圈的左上角是從坐(start,start)開始传蹈。
從以上分析押逼，我們可以得到，6>start*2,5>start*2惦界，也就是說最后一圈的左上角元素不能超過矩陣一半挑格。這個就是我們得到的邊界條件，沒循環(huán)一次打印一圈元素沾歪。那么打印一圈元素的函數(shù)又要如何實現(xiàn)呢漂彤？
這里需要分幾種情況，因為輸入的矩陣不一定是行列相等的灾搏，所以打印最后一圈元素會有一下幾種情況挫望。打印4步的，打印3步的狂窑，打印2步的和打印1步的媳板。
1.打印1步的：說明最后一圈只有一行元素，只用橫向打印起始橫坐標到終止點橫坐標之間的元素就可以泉哈。
2.打印2步的蛉幸，說明最后一圈只有一列，在第一次打印之后丛晦，需要縱向打印奕纫。前提條件就是終止行號大于起始行號。
3.打印3步的烫沙，說明至少有2行2列匹层，也就是終止行號大于起始行號，且終止列號大于起始列號锌蓄。
4.打印4步的升筏，說明至少有3行2列，也就是終止行號至少要比起始行號大2煤率，終止列號大于起始列號仰冠。
代碼
下面是代碼。在打印一圈時的幾次判斷比較容易出錯蝶糯，畫個圖分析一下就好了。
//打印一圈的元素,最多有4步
void PrintMatrixInCricule(int **numbers, int columns, int rows, int start)
{
int endX = columns - 1 - start;
int endY = rows - 1 - start;
//第一步辆沦，從左到右打印一行
for (int i = start; i <= endX; i++)
{
int number = numbers[start][i];
PrintNumber(number);
}
//第二步昼捍，從上到下打印一列
if (endY > start)
{
for (int i = start + 1; i <= endY; i++)
{
int number = numbers[i][endX];
PrintNumber(number);
}
}
//第三步，從右到左打印一行
if (endX > start && endY > start)
{
for (int i = endX - 1; i >= start; i--)
{
int number = numbers[endY][i];
PrintNumber(number);
}
}
//第四步肢扯，從下到上打印一列(2行3列)
if (endX > start && endY - 1 > start)
{
for (int i = enxY - 1; i > start; i--)
{
int number = numbers[i][start];
PrintNumber(number);
}
}
}
void PrintMatrix(int **numbers, int columns, int rows)
{
if (numbers == NULL || columns <= 0 || rows <= 0)
{
fprintf(stderr, "Invalid parameter妒茬！\n" );
exit(1);
}
int start = 0;
while (columns > start * 2 && rows > start * 2)
{
PrintMatrixInCricule(numbers, columns, rows, start);
start ++;
}
}
3.查找數(shù)組中出現(xiàn)次數(shù)大于一半的數(shù)字
問題描述：輸入一個數(shù)組，這個數(shù)組中有一個數(shù)字的個數(shù)超過一半蔚晨，查找這個數(shù)字乍钻。如{2,3,1,2,2,2,2,4,5},2有5個肛循，超過了一半，就返回2银择。
算法思想
思路一：看到這個題多糠，我們可能會想到，如果這個數(shù)組是排好序的就好了浩考，和上次的“數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)” 的思路類似夹孔，我們可以在O(logn)時間內解決這個問題。
思路二：利用數(shù)組呃特點析孽，在O(n)內找到這個數(shù)字搭伤。既然數(shù)組中存在一個數(shù)字出現(xiàn)的次數(shù)大于數(shù)組長度一半，那么可以確定這個數(shù)字出現(xiàn)的次數(shù)大于其他數(shù)字出現(xiàn)次數(shù)的總和袜瞬。我們考慮在遍歷數(shù)組的時候保存兩個值怜俐，一個是數(shù)字，一個是數(shù)字出現(xiàn)的次數(shù)邓尤。當我們遍歷到下一個元素時佑菩，如果這個數(shù)字和上一次保存的結果相同，次數(shù)+1裁赠；如果不同殿漠，次數(shù)-1，當次數(shù)減到0的時候佩捞，將保存的結果設置為當前的數(shù)字绞幌。由于我們要找的數(shù)字出現(xiàn)的次數(shù)總是最大的，所以最后一個把次數(shù)設置為1的數(shù)字就是我們要找的數(shù)字一忱。遍歷的時間復雜度為O(n).所以整個算法的時間復雜度也是O(n).
代碼
基于思路二的代碼莲蜘，注意，我們不知道傳入的的數(shù)組是否符合規(guī)格帘营，有出現(xiàn)次數(shù)超過一半的數(shù)字票渠，所以我們最后還需要驗證一下。
int MoreThanHalfNum(int *numbers, int length)
{
if (numbers == NULL || length <= 0)
{
g_bInvalidInput = true;
fprintf(stderr, "Invalid parameter\n");
exit(1);
}
int result = numbers[0];
int times = 1;
for (int i = 1; i < length; i++)
{
if (times == 0)
{
result = numbers[i];
times = 1;
}
else if (result == numbers[i])
times ++;
else
times --;
}
if(!CheckMoreThanHalf(numbers, length, result))
return 0;
return result;
}
驗證數(shù)組中是否存在出現(xiàn)次數(shù)超過一半的數(shù)字芬迄。
//檢查數(shù)組中是否有超過一半的數(shù)字
bool CheckMoreThanHalf(int *number, int length, int result)
{
int time = 0;
for (int i = 0; i < length; i++)
{
if (numbers[i] == result)
time++;
}
bool isMoreThanHalf = true;
if (time * 2 < length)
{
g_bInvalidInput = true;
isMoreThanHalf = false;
}
return isMoreThanHalf;
}
總結
這次的3道題難度都不大问顷，主要是分析問題，發(fā)現(xiàn)數(shù)組的特征禀梳。在調整數(shù)組順序杜窄，使奇數(shù)位于偶數(shù)前面中，技巧在于使用2個指針來分開元素算途，這一系列的題都可以這樣解決塞耕，關鍵只是修改判斷條件。在順時針打印矩陣中嘴瓤，主要把打印矩陣這一模型簡化為一個一個圈扫外，然后分析打印每一圈的步驟莉钙，確定邊界條件。在查找數(shù)組中出現(xiàn)次數(shù)大于一半的數(shù)字中筛谚，主要是分析這一數(shù)組的特點磁玉，要找的這個數(shù)字出現(xiàn)的次數(shù)一定大于其他數(shù)字出現(xiàn)次數(shù)之和，利用好這個特點刻获，代碼就簡單多了蜀涨。好了，這次就到這里了蝎毡，不足之處厚柳，歡迎指教~
