面試算法代碼知識(shí)梳理系列
面試算法知識(shí)梳理(1) - 排序算法
面試算法知識(shí)梳理(2) - 字符串算法第一部分
面試算法知識(shí)梳理(3) - 字符串算法第二部分
面試算法知識(shí)梳理(4) - 數(shù)組第一部分
面試算法知識(shí)梳理(5) - 數(shù)組第二部分
面試算法知識(shí)梳理(6) - 數(shù)組第三部分
面試算法知識(shí)梳理(7) - 數(shù)組第四部分
面試算法知識(shí)梳理(8) - 二分查找算法及其變型
面試算法知識(shí)梳理(9) - 鏈表算法第一部分
面試算法知識(shí)梳理(10) - 二叉查找樹
面試算法知識(shí)梳理(11) - 二叉樹算法第一部分
面試算法知識(shí)梳理(12) - 二叉樹算法第二部分
面試算法知識(shí)梳理(13) - 二叉樹算法第三部分
一固棚、概要
本文介紹了有關(guān)數(shù)組的算法第三部分的Java代碼實(shí)現(xiàn)委造，所有代碼均可通過 在線編譯器 直接運(yùn)行妄迁，算法目錄：
- 在遞增排序的數(shù)組中，查找指定數(shù)字出現(xiàn)的個(gè)數(shù)
- 查找數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字
- 在遞增排序的數(shù)組中岸啡，查找和為
s的兩個(gè)數(shù) - 輸入一個(gè)正數(shù)
s翎承，打印出所有和為s的連續(xù)正數(shù)序列 - 數(shù)組當(dāng)中的最大最小值
二顾画、代碼實(shí)現(xiàn)
2.1 在遞增排序的數(shù)組中滨砍，查找指定數(shù)字出現(xiàn)的個(gè)數(shù)
問題描述
在遞增排序的數(shù)組中，查找指定數(shù)字出現(xiàn)的個(gè)數(shù)
解決思路
這個(gè)問題的關(guān)鍵信息是輸入數(shù)組是 遞增排序 的纷跛，指定數(shù)字必然是連在一起的喻括，因此，我們只需要找到該數(shù)字第一次和最后一次出現(xiàn)的下標(biāo)位置贫奠，那么就可以得到該數(shù)字出現(xiàn)的數(shù)字唬血。
對(duì)于遞增排序的數(shù)組，最常見的方法就是使用 二分查找唤崭，以查找數(shù)字第一次出現(xiàn)的位置為例拷恨，也就是下面的getFirstK函數(shù)：
- 如果只有一個(gè)元素，那么判斷該元素是否是指定數(shù)字即可
- 如果只有兩個(gè)元素谢肾，那么先判斷前面的元素腕侄，如果不相等再判斷后面的元素
- 如果大于兩個(gè)元素，那么取中點(diǎn)位置的元素芦疏，如果該元素比需要查找的數(shù)字小冕杠，那么就說明需要查找的元素在其右側(cè)，否則就說明它在查找元素的左側(cè)（有可能包含該中點(diǎn)位置元素）酸茴。
getLastK也是同理分预。
代碼實(shí)現(xiàn)
class Untitled {
static int getFirstK(int p[], int num, int startIndex, int endIndex) {
if (endIndex == startIndex) {
return p[startIndex] == num ? startIndex : -1;
}
if (endIndex-startIndex == 1) {
if (p[startIndex] == num) {
return startIndex;
} else if (p[endIndex] == num) {
return endIndex;
} else {
return -1;
}
}
int midOffset = (endIndex-startIndex) >> 1;
//如果中間的元素比尋找的小，那么說明其在中間元素的右側(cè)薪捍。
if (p[startIndex+midOffset] < num) {
return getFirstK(p, num, startIndex+midOffset+1, endIndex);
} else {
return getFirstK(p, num, startIndex, startIndex+midOffset);
}
}
static int getLastK(int p[], int num, int startIndex, int endIndex) {
if (endIndex == startIndex) {
return p[startIndex] == num ? startIndex : -1;
}
if (endIndex-startIndex == 1) {
if (p[endIndex] == num) {
return endIndex;
} else if (p[startIndex] == num) {
return startIndex;
} else {
return -1;
}
}
int midOffset = (endIndex-startIndex) >> 1;
if (p[startIndex+midOffset] <= num) {
return getLastK(p, num, startIndex+midOffset, endIndex);
} else {
//如果中間的元素比尋找的大笼痹，那么說明其在中間元素的左側(cè)。
return getLastK(p, num, startIndex, startIndex+midOffset-1);
}
}
static int getNumberAppearTimes(int p[], int num, int len) {
int firstK = getFirstK(p, 6, 0, len-1);
int lastK = getLastK(p, 6, 0, len-1);
if (firstK >= 0 && lastK >= 0) {
System.out.println("firstK=" + firstK + ",lastK=" + lastK);
}
return lastK-firstK+1;
}
public static void main(String[] args) {
int p[] = {1, 2, 3, 6, 6, 6, 9};
int result = getNumberAppearTimes(p, 6, 7);
System.out.println("appear=" + result);
}
}
運(yùn)行結(jié)果
>> firstK=3,lastK=5
>> appear=3
2.2 查找數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字
問題描述
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外酪穿，其他的數(shù)字都出現(xiàn)了兩次与倡，請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。
解決思路
首先昆稿，讓我們?cè)購(gòu)?fù)習(xí)一下異或的特點(diǎn)：兩個(gè)相同的數(shù)異或的結(jié)果為0纺座，且異或滿足交換律和結(jié)合律。
對(duì)于題目中的假設(shè)溉潭，假如這兩個(gè)只出現(xiàn)了一次的數(shù)為a和b：
- 第一步：對(duì)整型數(shù)組中的所有數(shù)進(jìn)行異或净响，那么得到的結(jié)果就是
a^b的值。 - 第二步：將
a和b分到兩個(gè)不同的子數(shù)組當(dāng)中喳瓣，再分別對(duì)這兩個(gè)數(shù)組進(jìn)行異或馋贤，那么就可以得到a和b了，而劃分的依據(jù)就是根據(jù)第一步的結(jié)果畏陕，找出a^b中為1的一位配乓。
代碼實(shí)現(xiàn)
class Untitled {
static void getTwoAppearOnce(int p[], int len) {
int excluX = 0;
int excluY = 0;
for (int i=0; i<len; i++) {
excluX ^= p[i];
}
System.out.println("全部異或結(jié)果=" + excluX);
if (excluX != 0) {
//確定兩個(gè)出現(xiàn)唯一的元素，有一位一個(gè)為1，另一個(gè)為0犹芹。
int diffBit = excluX^(excluX&(excluX-1));
System.out.println("不相同的位=" + diffBit);
excluX = 0;
for (int i=0; i<len; i++) {
//根據(jù)上面求出的位崎页，分成兩組，分別進(jìn)行異或操作腰埂。
if ((p[i] & diffBit) == 0) {
excluX ^= p[i];
} else {
excluY ^= p[i];
}
}
System.out.println("第一個(gè)元素=" + excluX + ",第二個(gè)元素=" + excluY);
}
}
public static void main(String[] args) {
int p[] = {1,3,3,5,7,7};
getTwoAppearOnce(p, p.length);
}
}
運(yùn)行結(jié)果
>> 全部異或結(jié)果=4
>> 不相同的位=4
>> 第一個(gè)元素=1,第二個(gè)元素=5
2.3 在遞增排序的數(shù)組中飒焦，查找和為 s 的兩個(gè)數(shù)
問題描述
在遞增排序的數(shù)組中，查找和為s的兩個(gè)數(shù)
解決思路
由于原數(shù)組是 遞增排序 的屿笼，因此我們可以定義兩個(gè)指針first和last牺荠，分別指向數(shù)組的首元素和尾元素，如果當(dāng)前的和小于sum驴一，那么說明需要放入一個(gè)更大的元素休雌，就可以將首指針前移，如果小于sum肝断，那么就將尾指針后移杈曲。
這里有一點(diǎn)需要注意，對(duì)于first和last已經(jīng)移動(dòng)過的位置孝情，可以 確定其所在的元素 一定不是符合條件的兩個(gè)數(shù)之一鱼蝉，因此，first不需要前移箫荡，last也不需要后移魁亦。
實(shí)現(xiàn)代碼
class Untitled {
static void findTwoNumberIsSumN(int p[], int len, int sum) {
int first = 0;
int last = len-1;
while(first <= last) {
int temp = p[first]+p[last];
if (temp == sum) {
System.out.println("p[first]=" + p[first] + ",p[last]=" + p[last]);
break;
} else if (temp < sum) {
first++;
} else {
last--;
}
}
}
public static void main(String[] args) {
int p[] = {1,2,4,7,11,15};
findTwoNumberIsSumN(p, p.length, 15);
}
}
運(yùn)行結(jié)果
p[first]=4,p[last]=11
2.4 輸入一個(gè)正數(shù) s，打印出所有和為 s 的連續(xù)正數(shù)序列
實(shí)現(xiàn)代碼
class Untitled {
static void getSerialNumberSumN(int sum) {
int startNum = 1;
int endNum = 2;
int curSum = startNum+endNum;
int max = (1+sum) >> 1;
while (startNum < max) {
if (curSum == sum) {
System.out.println("[" + startNum + "..." + endNum + "]");
}
//如果當(dāng)前的和大于要求的值羔挡，那么就移動(dòng)首元素洁奈，使得數(shù)組的范圍變小。
while (curSum > sum && startNum < max) {
//注意要先減再移位绞灼。
curSum = curSum-startNum;
startNum++;
if (curSum == sum) {
System.out.println("[" + startNum + "..." + endNum + "]");
}
}
//移動(dòng)尾元素利术，使得數(shù)組的范圍變大，注意要先移位之后再加低矮。
endNum++;
curSum = curSum+endNum;
}
}
public static void main(String[] args) {
getSerialNumberSumN(15);
}
}
運(yùn)行結(jié)果
>> [1...5]
>> [4...6]
>> [7...8]
2.5 數(shù)組當(dāng)中的最大最小值
實(shí)現(xiàn)代碼
class Untitled {
static class ValueHolder {
public int maxNum;
public int minNum;
}
static ValueHolder getMaxMinNumber(int p[], int startIndex, int endIndex) {
ValueHolder value = new ValueHolder();
if (startIndex == endIndex) {
value.maxNum = p[startIndex];
value.minNum = p[endIndex];
return value;
}
int midOffset = (endIndex-startIndex) >> 1;
ValueHolder l = getMaxMinNumber(p, startIndex, startIndex+midOffset);
ValueHolder r = getMaxMinNumber(p, startIndex+midOffset+1, endIndex);
if (l.maxNum >= r.maxNum) {
value.maxNum = l.maxNum;
} else {
value.maxNum = r.maxNum;
}
if (l.minNum < r.minNum) {
value.minNum = l.minNum;
} else {
value.minNum = r.minNum;
}
return value;
}
public static void main(String[] args) {
int p[] = {1,45,23,3,6,2,7,234,56};
ValueHolder v = getMaxMinNumber(p, 0, p.length-1);
System.out.println("max=" + v.maxNum + ",min=" + v.minNum);
}
}
運(yùn)行結(jié)果
>> max=234,min=1
更多文章印叁，歡迎訪問我的 Android 知識(shí)梳理系列：
- Android 知識(shí)梳理目錄：http://www.reibang.com/p/fd82d18994ce
- Android 面試文檔分享：http://www.reibang.com/p/8456fe6b27c4
