面試算法代碼知識梳理系列
面試算法知識梳理(1) - 排序算法
面試算法知識梳理(2) - 字符串算法第一部分
面試算法知識梳理(3) - 字符串算法第二部分
面試算法知識梳理(4) - 數(shù)組第一部分
面試算法知識梳理(5) - 數(shù)組第二部分
面試算法知識梳理(6) - 數(shù)組第三部分
面試算法知識梳理(7) - 數(shù)組第四部分
面試算法知識梳理(8) - 二分查找算法及其變型
面試算法知識梳理(9) - 鏈表算法第一部分
面試算法知識梳理(10) - 二叉查找樹
面試算法知識梳理(11) - 二叉樹算法第一部分
面試算法知識梳理(12) - 二叉樹算法第二部分
面試算法知識梳理(13) - 二叉樹算法第三部分
一、概要
本文介紹了有關(guān)數(shù)組的算法第二部分的Java
代碼實現(xiàn),所有代碼均可通過 在線編譯器 直接運(yùn)行藤肢,算法目錄:
- 找到最小的
k
個數(shù) - 連續(xù)子數(shù)組的最大和
- 連續(xù)子數(shù)組的最大和(二維)
- 求數(shù)組當(dāng)中的逆序?qū)?/li>
二、代碼實現(xiàn)
2.1 找到最小的 k 個數(shù)
問題描述
即尋找一列數(shù)中最小的k
個數(shù)
解決思路
利用最大堆的特點(diǎn)史侣,加入我們對一個長度為N
的數(shù)組p
的前k
個元素進(jìn)行建堆操作,那么p[0]
為p[0,..,k-1]
的最大值魏身,之后再對p[k,..,N-1]
依次遍歷:
- 如果
p[i]
小于p[0]
惊橱,那么就說明它屬于p[0,..,i]
最小的K
個元素之一,而p[0]
則一定不屬于p[0,..,N-1]
的最小的k
個元素箭昵,此時將p[i]
和p[0]
交換税朴,重新對[0,..,N-1]
的部分進(jìn)行建堆操作 - 如果
p[i]
大于等于p[0]
,那么就說明p[i]
一定不屬于p
中最小的k
個元素家制,因此忽略
直到i
遍歷到N-1
為止正林,此時p[0,..,k-1]
就是數(shù)組p
最小的K
個元素。
代碼實現(xiàn)
class Untitled {
static void maxHeapify(int p[], int di, int length){
int li = (di<<1)+1;
int t = p[di];
while (li < length) {
if (li+1 < length && p[li+1] > p[li])
li++;
if (p[di] >= p[li])
break;
p[di] = p[li];
di = li;
li = (di<<1)+1;
}
p[di] = t;
}
static void buildMaxHeap(int p[], int length){
for(int i=(length>>1)-1; i >= 0; i--){
maxHeapify(p, i, length);
}
}
static void minKthNum(int p[] ,int k, int length) {
buildMaxHeap(p,k);
int t;
for (int i=k; i < length; i++) {
if (p[i] < p[0]) {
t = p[0]; p[0] = p[i]; p[i] = t;
maxHeapify(p, 0, k);
}
}
}
public static void main(String[] args) {
int p[] = new int[]{2, 3, 10, 2, 5, 6, 7, 20, 1, -5};
minKthNum(p, 3, p.length);
for (int i=0; i < 3; i++) {
System.out.println(String.valueOf(p[i]));
}
}
}
運(yùn)行結(jié)果
>> 2
>> 1
>> -5
2.2 連續(xù)字?jǐn)?shù)組的最大和
問題描述
數(shù)組中的元素有正有負(fù)慰丛,在該數(shù)組中找出一個連續(xù)子數(shù)組卓囚,要求該連續(xù)子數(shù)組中各元素的和最大瘾杭,這個連續(xù)子數(shù)組便被稱作最大連續(xù)子數(shù)組诅病。比如數(shù)組{2,4,-7,5,2,-1,2,-4,3}
的最大連續(xù)子數(shù)組為{5,2,-1,2}
,最大連續(xù)子數(shù)組的和為5+2-1+2=8
粥烁。
解決思路
通過對數(shù)組中的元素進(jìn)行線性的遍歷贤笆,并對每個元素進(jìn)行累加,當(dāng)發(fā)現(xiàn)目前為止累加的和maxendinghere
小于0
時讨阻,則說明最大的連續(xù)子數(shù)組不可能包含目前遍歷到的子數(shù)組芥永,那么就從下一個元素tmaxbegin
開始計算子數(shù)組。
在遍歷的過程中更新目前位置獲得的最大連續(xù)子數(shù)組的和maxsofar
钝吮,以及起止位置maxbegin
和maxend
埋涧。
代碼實現(xiàn)
class Untitled {
static void maxSumSubArray(int p[], int length){
int maxendinghere = 0;
int maxsofar = 0;
int maxbegin = 0;
int maxend = 0;
int tmaxbegin = 0;
//從0開始遍歷數(shù)組。
for(int i = 0; i < length; i++){
//maxendinghere 記錄當(dāng)前計算子數(shù)組的和奇瘦。
maxendinghere += p[i];
//如果該和小于0棘催,那么重新計算。
if(maxendinghere < 0){
maxendinghere = 0;
tmaxbegin = i+1;
}
//更新目前為止計算到的最大值耳标。
if(maxsofar < maxendinghere){
maxbegin = tmaxbegin;
maxend = i;
maxsofar = maxendinghere;
}
}
//考慮數(shù)組全部是負(fù)數(shù)的情況
if(maxsofar == 0){
maxsofar = p[0];
for(int i = 1; i < length; i++){
if(p[i] > maxsofar){
maxsofar = p[i];
maxbegin = i;
maxend = i;
}
}
}
for (int i = maxbegin; i <= maxend; i++) {
System.out.println("i=" + p[i]);
}
}
public static void main(String[] args) {
int p[] = new int[]{2,4,-7,5,2,-1,2,-4,3};
maxSumSubArray(p, p.length);
}
}
運(yùn)行結(jié)果
> i=5
> i=2
> i=-1
> i=2
2.3 連續(xù)子數(shù)組的最大和(二維)
問題描述
這個問題其實是2.2
的變種醇坝,這時候輸入是一個二維的矩陣,需要找到一個子矩陣次坡,該子矩陣的和是這個二維的所有子矩陣中最大的呼猪。
解決思路
二維的問題和2.2
中的一維問題的核心解決思路相同画畅。
對于二維情況,我們將 同一列的多個元素合并成一個元素 來實現(xiàn)降維的效果宋距,為了能實現(xiàn)在O(1)
的時間內(nèi)計算出同一列的多行元素之和轴踱,需要構(gòu)建一個輔助數(shù)組,該輔助數(shù)組ps[i][j]
的值谚赎,等于原輸入數(shù)組p
以p[0][0]
為左上角到p[i][j]
為右下角構(gòu)成的子矩陣的所有元素之和寇僧,通過該輔助數(shù)組就能在O(1)
的時間內(nèi)計算出lRow
到hRow
行之間第col
列的所有元素之和,計算公式為:
ps[hRow][col] - ps[hRow][col-1] - ps[lRow-1][col] + ps[lRow-1][col-1]
代碼實現(xiàn)
class Untitled {
//計算從lRow到hRow之間沸版,位于第col列的所有元素之和嘁傀。
static int getColsum(int ps[][], int lRow, int hRow, int col) {
return ps[hRow][col] - ps[hRow][col-1] - ps[lRow-1][col] + ps[lRow-1][col-1];
}
static void maxSumSubArray2(int p[][], int xlen, int ylen){
int maxendinghere = 0;
int maxsofar = 0;
int tColbegin = 1;
int sx = 0;
int sy = 0;
int ex = 0;
int ey = 0;
//初始化輔助數(shù)組,ps[i][j]為以其為右下角的子矩陣的所有元素之和视粮。
int psxLen = xlen+1;
int psyLen = ylen+1;
int[][] ps = new int[psxLen][psyLen];
for (int j = 0; j < psyLen; j++)
ps[0][j] = 0;
for (int i = 0; i < psxLen; i++)
ps[i][0] = 0;
for (int i = 1; i < psxLen; i++) {
for(int j = 1; j < psyLen; j++) {
ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + p[i-1][j-1];
}
}
//求矩陣中的最大和细办,將位于同一個列的多行元素合并成一個元素,因此需要遍歷包含不同行的情況蕾殴。
for (int pStartRow = 1; pStartRow < psxLen; pStartRow++) {
for (int pEndRow = pStartRow; pEndRow < psxLen; pEndRow++) {
for (int pCol = 1; pCol < psyLen; pCol++) {
maxendinghere += getColsum(ps, pStartRow, pEndRow, pCol);
if (maxendinghere < 0) {
maxendinghere = 0;
tColbegin = pCol+1;
}
if (maxsofar < maxendinghere) {
maxsofar = maxendinghere;
sx = pStartRow - 1;
sy = tColbegin - 1;
ex = pEndRow - 1;
ey = pCol - 1;
}
}
maxendinghere = 0;
tColbegin = 1;
}
}
System.out.println("最大和=" + maxsofar + ",起始行=" + sx + ",終止行=" + ex + ",起始列=" + sy + ",終止列=" + ey);
}
public static void main(String[] args) {
int[][] p = {{1,-10,-11}, {4,5,6}, {7,8,9}};
maxSumSubArray2(p, 3, 3);
}
}
運(yùn)行結(jié)果
>> 最大和=39,起始行=1,終止行=2,起始列=0,終止列=2
2.4 求數(shù)組中的逆序?qū)?/h2>
問題描述
在數(shù)組中的兩個數(shù)字笑撞,如果 前面一個數(shù)字大于后面的數(shù)字,則這兩個數(shù)字組成一個 逆序?qū)?/strong>钓觉。輸入一個數(shù)組茴肥,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)。
解決思路
這里采用的是 歸并算法 的思想荡灾,歸并算法包含三個關(guān)鍵步驟:
- 分解:把長度為
n
的待排序列分解成兩個長度為n/2
的序列瓤狐。 - 治理:對每個子序列分別調(diào)用歸并排序,進(jìn)行遞歸操作批幌。當(dāng)子序列長度為
1
時础锐,序列本身有序,停止遞歸荧缘。 - 合并:合并每個排序好的子序列皆警。
對于上面的例子,我們將整個數(shù)組分解為A截粗、B
兩部分信姓,則整個數(shù)組的逆序?qū)€數(shù)就等于:
A部分組成的數(shù)組的逆序?qū)?+ B部分組成的數(shù)組的逆序?qū)?+ A與B之間的逆序?qū)?
這里有一個關(guān)鍵的點(diǎn),就是需要保證在計算A
與B
之間的逆序?qū)r绸罗,A
和B
內(nèi)的元素都是有序的意推。
class Untitled {
static int inversePairs(int p[], int startIndex, int endIndex) {
if (endIndex == startIndex) {
return 0;
}
if (endIndex-startIndex == 1) {
if (p[endIndex] < p[startIndex]) {
int temp = p[startIndex];
p[startIndex] = p[endIndex];
p[endIndex] = temp;
return 1;
} else {
return 0;
}
}
int midOffset = (endIndex-startIndex) >> 1;
int l = inversePairs(p, startIndex, startIndex+midOffset);
int r = inversePairs(p, startIndex+midOffset+1, endIndex);
return l + r + inverseCore(p, startIndex, midOffset, endIndex);
}
static int inverseCore(int p[], int startIndex, int midOffset, int endIndex) {
int totalLen = endIndex-startIndex+1;
int lLen = midOffset+1;
int rLen = totalLen-lLen;
int l[] = new int[lLen+1];
int r[] = new int[rLen+1];
int i = 0;
for (i=0; i<lLen; i++) {
l[i] = p[startIndex+i];
}
l[i] = 1 << 30;
for (i=0; i<rLen; i++) {
r[i] = p[startIndex+lLen+i];
}
r[i] = 1 << 30;
int c = 0;
i = 0;
int m = 0;
int n = 0;
while(i < totalLen) {
if (r[n] <= l[m]) {
p[startIndex+i] = r[n];
c += (lLen - m);
n++;
i++;
} else {
p[startIndex+i] = l[m];
m++;
i++;
}
}
return c;
}
public static void main(String[] args) {
int[] p = {7,5,6,4};
System.out.println("Inverse Count=" + inversePairs(p, 0, 3));
}
}
運(yùn)行結(jié)果
>> Inverse Count=5
更多文章,歡迎訪問我的 Android 知識梳理系列:
- Android 知識梳理目錄:http://www.reibang.com/p/fd82d18994ce
- Android 面試文檔分享:http://www.reibang.com/p/8456fe6b27c4