面試算法知識梳理(5) - 數(shù)組第二部分

面試算法代碼知識梳理系列

面試算法知識梳理(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钝吮,以及起止位置maxbeginmaxend埋涧。

代碼實現(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ù)組pp[0][0]為左上角到p[i][j]為右下角構(gòu)成的子矩陣的所有元素之和寇僧,通過該輔助數(shù)組就能在O(1)的時間內(nèi)計算出lRowhRow行之間第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),就是需要保證在計算AB之間的逆序?qū)r绸罗,AB內(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 知識梳理系列:

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末从诲,一起剝皮案震驚了整個濱河市左痢,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌,老刑警劉巖俊性,帶你破解...
    沈念sama閱讀 218,036評論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件略步,死亡現(xiàn)場離奇詭異,居然都是意外死亡定页,警方通過查閱死者的電腦和手機(jī)趟薄,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,046評論 3 395
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來典徊,“玉大人杭煎,你說我怎么就攤上這事∽渎洌” “怎么了羡铲?”我有些...
    開封第一講書人閱讀 164,411評論 0 354
  • 文/不壞的土叔 我叫張陵,是天一觀的道長儡毕。 經(jīng)常有香客問我也切,道長,這世上最難降的妖魔是什么腰湾? 我笑而不...
    開封第一講書人閱讀 58,622評論 1 293
  • 正文 為了忘掉前任雷恃,我火速辦了婚禮,結(jié)果婚禮上费坊,老公的妹妹穿的比我還像新娘倒槐。我一直安慰自己,他們只是感情好附井,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,661評論 6 392
  • 文/花漫 我一把揭開白布讨越。 她就那樣靜靜地躺著虎眨,像睡著了一般。 火紅的嫁衣襯著肌膚如雪桨武。 梳的紋絲不亂的頭發(fā)上揭保,一...
    開封第一講書人閱讀 51,521評論 1 304
  • 那天,我揣著相機(jī)與錄音幸逆,去河邊找鬼。 笑死,一個胖子當(dāng)著我的面吹牛漫雕,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播峰鄙,決...
    沈念sama閱讀 40,288評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼浸间,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了吟榴?” 一聲冷哼從身側(cè)響起魁蒜,我...
    開封第一講書人閱讀 39,200評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后兜看,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體锥咸,經(jīng)...
    沈念sama閱讀 45,644評論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,837評論 3 336
  • 正文 我和宋清朗相戀三年细移,在試婚紗的時候發(fā)現(xiàn)自己被綠了搏予。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,953評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡弧轧,死狀恐怖雪侥,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情精绎,我是刑警寧澤速缨,帶...
    沈念sama閱讀 35,673評論 5 346
  • 正文 年R本政府宣布,位于F島的核電站代乃,受9級特大地震影響鸟廓,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜襟己,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,281評論 3 329
  • 文/蒙蒙 一引谜、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧擎浴,春花似錦员咽、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,889評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至仿吞,卻和暖如春滑频,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背唤冈。 一陣腳步聲響...
    開封第一講書人閱讀 33,011評論 1 269
  • 我被黑心中介騙來泰國打工峡迷, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人你虹。 一個月前我還...
    沈念sama閱讀 48,119評論 3 370
  • 正文 我出身青樓绘搞,卻偏偏與公主長得像,于是被迫代替她去往敵國和親傅物。 傳聞我的和親對象是個殘疾皇子夯辖,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,901評論 2 355

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,744評論 0 33
  • 1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表 題目: 輸入一棵二元查找樹董饰,將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表蒿褂。 要求不...
    曲終人散Li閱讀 3,314評論 0 19
  • Java經(jīng)典問題算法大全 /*【程序1】 題目:古典問題:有一對兔子圆米,從出生后第3個月起每個月都生一對兔子,小兔子...
    趙宇_阿特奇閱讀 1,868評論 0 2
  • 數(shù)組在程序設(shè)計中啄栓,為了處理方便榨咐, 把具有相同類型的若干變量按有序的形式組織起來。這些按序排列的同類數(shù)據(jù)元素的集合稱...
    朱森閱讀 3,926評論 2 13
  • 六年前谴供, 我遇見了你块茁, 那時, 就單戀著你桂肌。 時間数焊, 無情的流逝, 漸漸淡去的感情崎场, 已不復(fù)存在佩耳。 單戀這點(diǎn)小事,...
    龍諭閱讀 314評論 9 6