數(shù)組的相關(guān)算法要簡(jiǎn)單一些茸歧，之前寫(xiě)過(guò)的和現(xiàn)在遇到的整理了一下倦炒。
數(shù)組：數(shù)組是較為簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，它占據(jù)一塊連續(xù)的內(nèi)存软瞎，并按照順序存儲(chǔ)數(shù)據(jù)逢唤。數(shù)組需要事先知道容量大小，然后根據(jù)大小分配存儲(chǔ)空間涤浇，所以數(shù)組的空間利用率不高鳖藕。數(shù)組有很好的查找效率，能在O(1)內(nèi)找到元素只锭。所以我們可以基于數(shù)組實(shí)現(xiàn)簡(jiǎn)單的hash表著恩，提高查找效率。
數(shù)組和指針的關(guān)系：在C語(yǔ)言中蜻展，我們聲明一個(gè)數(shù)組時(shí)喉誊，數(shù)組名也是一個(gè)指針，數(shù)組有大小的限制纵顾，但是指針沒(méi)有限制伍茄，所以在使用指針訪問(wèn)數(shù)組時(shí)，要注意不能越界施逾。對(duì)數(shù)組和指針求sizeof時(shí)敷矫，有以下需要注意的地方：
1.int data[] = {0,1,2,3,4};對(duì)data求sizeof是20，因?yàn)閿?shù)組中有5個(gè)整數(shù)音念，每個(gè)整數(shù)占4個(gè)字節(jié)沪饺。
2.int *pData = data;對(duì)pData求sizeof是4，因?yàn)閜Data聲明為一個(gè)指針闷愤，在32位系統(tǒng)中整葡，對(duì)任意指針求sizeof結(jié)果都是4。
3.void fun(int data[]){...}讥脐；在函數(shù)中對(duì)data求sizeof時(shí)遭居，結(jié)果是4，因?yàn)镃語(yǔ)言中將數(shù)組作為參數(shù)傳遞時(shí)旬渠，會(huì)自動(dòng)退化為指針俱萍，結(jié)果還是4.
概念就介紹這些，進(jìn)入正題告丢。
- 二維數(shù)組中的查找
- 旋轉(zhuǎn)數(shù)組的最小數(shù)字
- 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
1.二維數(shù)字中的查找
問(wèn)題描述：每行從左到右枪蘑，每列從上到下遞增的二維數(shù)組中，判斷某個(gè)數(shù)是否存在。
算法思想
思路一：常規(guī)思路岳颇，我們很快就能想到遍歷二維數(shù)組照捡，和要查找的數(shù)字比較，判斷是否存在话侧。這樣的方法時(shí)間復(fù)雜度為O(n^2)栗精，效率很低。
思路二：我們可以利用遞增的二維數(shù)組的特點(diǎn)瞻鹏，選定數(shù)組中的一個(gè)點(diǎn)悲立，和要查找的key比較，如果key大于這個(gè)數(shù)新博，就在這個(gè)數(shù)的下面和右邊查找薪夕，如果小于這個(gè)數(shù)，就在這個(gè)數(shù)的上面和左邊查找赫悄，這個(gè)方法要比一個(gè)一個(gè)遍歷好寥殖，但是存在一個(gè)問(wèn)題，就是上面和右邊方向上的查找會(huì)有重復(fù)的查找的地方涩蜘。
思路三：在思路二上進(jìn)行改進(jìn)。我們之前的查找都是從左上角開(kāi)始熏纯，那么從右上角開(kāi)始呢同诫？以上的矩陣，假如我們查找的是7樟澜，從右上角開(kāi)始误窖，先比較9和7，9比7大秩贰，9又是本列的第一個(gè)霹俺，那么可以確定，9所在的列數(shù)字都大于7毒费，我們可以排除最后一列丙唧，前移一列。比較8和7觅玻，8大于7想际，同樣的思想我們可以排除8所在的列。接下來(lái)比較2和7溪厘，2小于7胡本，那么2所在的行前面的數(shù)字都小于7，可以不必再比較了畸悬，直接排除2所在的行侧甫。以此類(lèi)推，我們很快就可以定位到7。
代碼
思路清楚之后披粟，代碼就簡(jiǎn)單多了咒锻。
從矩陣的右上角開(kāi)始進(jìn)行判斷，最快的排除不需要比較的列和行
1.當(dāng)前元素>number,那么當(dāng)前元素所在的行就可以排除-->縮小比較范圍
2.當(dāng)前元素<number僻爽，那么當(dāng)前元素所在列可以排除
3.當(dāng)前元素=number虫碉，返回true
注：傳入二維數(shù)組的時(shí)候被強(qiáng)轉(zhuǎn)成了指針，所以在取出二維數(shù)組中的數(shù)字時(shí)胸梆，要更具指針的操作規(guī)范來(lái)敦捧。
bool Find(int* matrix, int rows, int columns, int number)
{
bool found = false;
if (matrix != NULL && rows > 0 && columns > 0)
{
int row = 0;
int column = columns - 1;
while (row < rows && column >= 0)
{
if (matrix[row * columns + column] == number){//相當(dāng)于matrix[row][column]
found = true;
break;
}
else if (matrix[row * columns + column] > number)
column--;
else
row++;
}
}
return found;
}
旋轉(zhuǎn)數(shù)組的最小數(shù)字
問(wèn)題描述：把數(shù)組開(kāi)頭的幾個(gè)數(shù)字移動(dòng)到數(shù)組的末尾，成為數(shù)組的旋轉(zhuǎn)碰镜，輸入一個(gè)遞增數(shù)組的旋轉(zhuǎn)兢卵，找到數(shù)組中最小的數(shù)字。
算法思想
思路一：一次遍歷就可以找到最小的數(shù)字绪颖。時(shí)間復(fù)雜度為O(n).
思路二：利用遞增數(shù)組的特點(diǎn)秽荤，利用二分法查找。我們可以發(fā)現(xiàn)遞增數(shù)組旋轉(zhuǎn)之后之后可以得到兩個(gè)排序的子數(shù)組柠横，且第一個(gè)數(shù)字會(huì)大于或者等于最后一個(gè)數(shù)字窃款，兩個(gè)排序子數(shù)組的分界點(diǎn)就是這個(gè)最小的數(shù)字，這樣在一定程度上排序的數(shù)組牍氛，我們可以嘗試使用二分法的思想晨继。使用兩個(gè)指針，一個(gè)指向數(shù)組頭搬俊，一個(gè)指向數(shù)組尾紊扬，接下來(lái)可以找到中間元素，如果中間元素大于第一個(gè)元素唉擂，中間元素位于前面的子數(shù)組中餐屎，就把前一個(gè)指針移動(dòng)到中間元素的位置；如果中間元素小于后一個(gè)指針指向的元素玩祟，說(shuō)明中間元素位于后面的子數(shù)組中腹缩，就把后一個(gè)指針移到中間元素的位置，這樣就減少了一半查找范圍空扎。當(dāng)?shù)谝粋€(gè)指針和后一個(gè)指針相差1時(shí)庆聘，那么后一個(gè)指針?biāo)妇褪亲钚≡亓恕r(shí)間復(fù)雜度為O(logn).
改進(jìn)：以上思路還存在bug宴抚，我們開(kāi)考慮這樣的數(shù)組勒魔，如圖，在第一個(gè)數(shù)組中菇曲，我們定位到中間元素后發(fā)現(xiàn)冠绢，前一個(gè)指針?biāo)福虚g元素和后一個(gè)指針?biāo)付际且粯映３保绻@個(gè)時(shí)候簡(jiǎn)單的把中間元素歸到前一個(gè)子數(shù)組中弟胀，那么默認(rèn)最小元素在中間元素的后面就出錯(cuò)了。原因在于這樣的中間元素我們不能確定它是屬于后面還是屬于前面喊式，這時(shí)只能順序查找了孵户。
代碼
分析結(jié)束可以看代碼了献联。
注意：在Min函數(shù)中竖配，我們把indexMid初始化為index1，也就是指向第一個(gè)元素里逆，當(dāng)傳入的數(shù)組是遞增數(shù)組時(shí)（原數(shù)組本身也是數(shù)組的一個(gè)旋轉(zhuǎn)數(shù)組）进胯，第一個(gè)元素就是最小的，這時(shí)函數(shù)會(huì)返回第一個(gè)元素原押。
//當(dāng)index1,indexMid,index2所指元素都相等的時(shí)只能順序查找
int MinInOrder(int *numbers, int index1, int index2)
{
for (int i = index1 + 1; i <= index2; i++)
{
if (result > numbers[i])
{
return numbers[i];
}
}
return numbers[index1];
}
//查找旋轉(zhuǎn)數(shù)組中的最小數(shù)
int Min(int *numbers, int length)
{
if (numbers == NULL || length < 0)
{
fprintf(stderr, "Invalid parameter\n" );
exit(1);
}
int index1 = 0;
int index2 = length - 1;
int indexMid = index1;
while (numbers[index1] >= numbers[index2])
{
if ((index2 - index1) == 1)
{
indexMid = index2;
break;
}
indexMid = (index2 + index1) / 2;
//特殊情況龄减，無(wú)法判斷indexMid是屬于哪一個(gè)子數(shù)組
if (numbers[index1] == numbers[indexMid] && numbers[indexMid] == numbers[index2])
return MinInOrder(numbers, index1, index2);
//中間元素屬于前一個(gè)子數(shù)組
if (numbers[indexMid] > numbers[index1])
index1 = indexMid;
else if (numbers[indexMid] < numbers[index2])
index2 = indexMid;
}
return numbers[indexMid];
}
數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
問(wèn)題描述：統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。如果數(shù)組{1,2,3,3,3,3,4,5}和數(shù)字3,3在數(shù)組中出現(xiàn)了4次班眯，返回4.
這個(gè)可以看做是查找問(wèn)題，關(guān)注排序數(shù)組幾個(gè)字。
算法思想
思路一：最簡(jiǎn)單直接的思路就是一次遍歷數(shù)組，進(jìn)行統(tǒng)計(jì)讨阻，時(shí)間復(fù)雜度為O(n)仁烹。
思路二：常規(guī)的思路人人都能想到，雖然簡(jiǎn)單句惯，但是考慮到數(shù)組的特點(diǎn)，注意，這里的數(shù)組是排序數(shù)組诊霹。說(shuō)到排序數(shù)組，我們可以想到二分查找渣淳，那么如果把二分查找的思想遷移到這里呢脾还？先找到最中間的元素，如果最中間的元素小于或者大于要統(tǒng)計(jì)次數(shù)的數(shù)字入愧，那么范圍減少一半鄙漏，其實(shí)提高了效率嗤谚，但是如果最中間的數(shù)組等于要查找的數(shù)字呢？我們就需要向兩邊查找怔蚌，一直找到第一個(gè)數(shù)字和最后一個(gè)數(shù)字巩步，數(shù)字在長(zhǎng)度為n的數(shù)組中有可能出現(xiàn)n次，所以桦踊，時(shí)間復(fù)雜度為O(n),和思路一的時(shí)間復(fù)雜度相同了椅野。
思路三：思路二的改進(jìn)。假設(shè)要統(tǒng)計(jì)次數(shù)的數(shù)字為key,在思路二中籍胯，時(shí)間耗費(fèi)主要是在確定第一個(gè)key和最后一個(gè)key的時(shí)候竟闪，那么如果用二分法獲取第一個(gè)key和最后一個(gè)key的位置呢？先找到中間數(shù)字芒炼，如果比key小瘫怜，說(shuō)明第一個(gè)key在后半部分，如果比key大本刽，說(shuō)明第一個(gè)key在前半部分鲸湃，如果相等的話，先看中間數(shù)字的前一個(gè)是不時(shí)也等于key子寓，如果不等暗挑，就可以確定中間數(shù)字就是第一個(gè)key，如果相等斜友，說(shuō)明第一個(gè)key在前一半炸裆，繼續(xù)查找，找最后一個(gè)key的方法也類(lèi)似鲜屏，可以用遞歸實(shí)現(xiàn)烹看。這樣的算法，找第一個(gè)key的時(shí)候時(shí)間復(fù)雜度為O(logn)洛史，找最后一個(gè)key的時(shí)候惯殊，時(shí)間復(fù)雜度也是O(logn)，所以總的時(shí)間復(fù)雜度也是O(logn)也殖。
代碼
下面是思路三的代碼土思，有以下需要注意的地方：
- 在FindFirstK和FindLastK函數(shù)中，在判斷中間元素的前一個(gè)元素或后一個(gè)元素是否是key時(shí)忆嗜，要先判斷是否到達(dá)數(shù)組邊界己儒，防止越界。
- 在函數(shù)GetNumberOfK中捆毫，計(jì)算key出現(xiàn)的次數(shù)時(shí)先判斷了firstIndex和lastIndex是否都大于-1闪湾，這是因?yàn)橹灰幸粋€(gè)值為-1，那么數(shù)組中就不可能存在這個(gè)key绩卤。因?yàn)樵贔indFirstK和FindLastK中响谓，只有找不到key才會(huì)返回-1损合，既然數(shù)組中沒(méi)有key，那么自然就不會(huì)執(zhí)行middle==key下面的判斷了娘纷，而這里嫁审，就是FindFirstK和FindLastK兩個(gè)函數(shù)不同的地方。也就是說(shuō)赖晶，當(dāng)數(shù)組中沒(méi)有key時(shí)律适，F(xiàn)indFirstK和FindLastK兩個(gè)函數(shù)執(zhí)行的過(guò)程都是一樣的。所以遏插，我們也可以改進(jìn)下面的代碼捂贿，在GetNumberOfK中，計(jì)算了firstIndex之后先判斷其是否等于-1胳嘲，如果等于-1就厂僧，不必再計(jì)算lastIndex了，直接返回0.
//遞歸確定第一個(gè)key的下標(biāo)
int FindFirstK(int *data, int length, int start, int end, int key)
{
if (start > end)
return -1;
int middleIndex = (start + end) / 2;
int middle = data[middleIndex];
if (middle == key)
{
//先判斷是否大于0了牛，再計(jì)算data[middleIndex-1]防止越界
if ((middleIndex > 0 && data[middleIndex - 1] != key)
|| middleIndex == 0)
return middleIndex;
else
end = middleIndex - 1;
}
else if (middle < key)
start = middleIndex + 1;
else//middle > key
end = middleIndex - 1;
FindFirstK(data, length, start, end, key);
}
//遞歸確定最后一個(gè)key的位置
int FindLastK(int *data, int length, int start, int end, int key)
{
if (start > end)
return -1;
int middleIndex = (start + end) / 2;
int middle = data[middleIndex];
if (middle == key)
{
if ((middleIndex < length - 1 && data[middleIndex + 1] != key)
|| middleIndex == length - 1)
return middleIndex;
else
start = middleIndex + 1;
}
else if (middle < key)
start = middleIndex + 1;
else//middle > key
end = middleIndex - 1;
FindLastK(data, length, start, end, key);
}
int GetNumberOfK(int *data, int length, int key)
{
int count = 0;
if (data != NULL || length > 0)
{
int firstIndex = FindFirstK(data, length, 0, length - 1, key);
int lastIndex = FindLastK(data, length, 0, length - 1, key);
if (firstIndex > -1 && lastIndex > -1)
count = lastIndex - firstIndex + 1;
}
return count;
}
總結(jié)
這次的三道題說(shuō)是數(shù)組相關(guān)的算法題颜屠，也可以說(shuō)是和查找算法題，在二維數(shù)組中的查找中鹰祸，我們利用了二維遞增數(shù)組的規(guī)律甫窟，每次都找右上角的數(shù)組，便于快速排出行或者列蛙婴；在旋轉(zhuǎn)數(shù)組的最小數(shù)字和計(jì)算數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)中粗井，我們利用了排序數(shù)組的特點(diǎn)，用二分法進(jìn)行查找街图，其實(shí)是遷移了二分查找的思想浇衬，進(jìn)行了變換得到的。
好了餐济，這次就到這里了耘擂。不足之處，還請(qǐng)多指教颤介。
