欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java面試題沖刺第二十三天--算法(2)

 更新時間:2021年08月09日 11:25:31   作者:_陳哈哈  
這篇文章主要為大家分享了最有價值的三道關(guān)于算法的面試題,涵蓋內(nèi)容全面,包括數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的題目、經(jīng)典面試編程題等,感興趣的小伙伴們可以參考一下

面試題1:你說一下常用的排序算法都有哪些?

在這里插入圖片描述

追問1:談一談你對快排的理解吧

快速排序,顧名思義就是一種以效率快為特色的排序算法,快速排序(Quicksort)是對冒泡排序的一種改進(jìn)。由英國計算機(jī)專家:托尼·霍爾(Tony Hoare)在1960年提出。

從排序數(shù)組中找出一個數(shù),可以隨機(jī)取,也可以取固定位置,一般是取第一個或最后一個,稱為基準(zhǔn)數(shù)。然后將比基準(zhǔn)小的排在左邊,比基準(zhǔn)大的放到右邊;

如何放置呢,就是和基準(zhǔn)數(shù)進(jìn)行交換,交換完左邊都是比基準(zhǔn)小的,右邊都是比較基準(zhǔn)大的,這樣就將一個數(shù)組分成了兩個子數(shù)組,然后再按照同樣的方法把子數(shù)組再分成更小的子數(shù)組,直到不能分解(子數(shù)組只有一個值)為止。以此達(dá)到整個數(shù)據(jù)變成有序序列。

在這里插入圖片描述

快速排序采用了一種分治的策略,通常稱其為分治法(Divide-and-ConquerMethod),現(xiàn)在各種語言中自帶的排序庫很多使用的都是快速排序。

空間復(fù)雜度

快速排序是一種原地排序,只需要一個很小的棧作為輔助空間,空間復(fù)雜度為O(log2n),所以適合在數(shù)據(jù)集比較大的時候使用。

時間復(fù)雜度

時間復(fù)雜度比較復(fù)雜,最好的情況是O(n),最差的情況是O(n2),所以平時說的O(nlogn),為其平均時間復(fù)雜度。

  • O(n):理想的情況,每次劃分所選擇的中間數(shù)恰好將當(dāng)前序列幾乎等分,經(jīng)過log2n趟劃分,便可得到長度為1的子表。這樣,整個算法的時間復(fù)雜度為O(nlog2n)。
  • O(n2):最壞的情況,每次所選的中間數(shù)是當(dāng)前序列中的最大或最小元素,這使得每次劃分所得的子表中一個為空表,另一子表的長度為原表的長度-1。這樣,長度為n的數(shù)據(jù)表的快速排序需要經(jīng)過n趟劃分,使得整個排序算法的時間復(fù)雜度為O(n2)。

追問2:說一下快排的算法原理

算法步驟

  • 選定一個基準(zhǔn)數(shù)(一般取第一位數(shù)字)作為中心點(diǎn)(Pivot);
  • 將大于Pivot的數(shù)字放到Pivot的左邊;
  • 將小于Pivot的數(shù)字放到Pivot的右邊;
  • 第一次排序結(jié)束后,分別對左右子序列繼續(xù)遞歸重復(fù)前三步操作,直到左右子序列長度只有單個元素為止。

在這里插入圖片描述

demo示例

實(shí)例數(shù)組:arr[] = {19,97,9,17,1,8};

在這里插入圖片描述

取出基準(zhǔn)數(shù)Pivot,以該值為中心軸。

快速排序中的規(guī)則:右邊有坑,就從左邊Arr[L + n]取值來填,反之左邊有坑,則從右邊Arr[R - n]取值來填;

在這里插入圖片描述

從左邊取的基準(zhǔn)值,左邊的Arr[L]就空出來了,則先從右側(cè)取值來填,從最右側(cè)下標(biāo)開始,在Arr[R] 取到第一個值“8”;

在這里插入圖片描述

將取到的Arr[R]與基準(zhǔn)值比較,發(fā)現(xiàn)小于基準(zhǔn)值,則插入到Arr[R],占到了基準(zhǔn)值Pivot的位置上。

在這里插入圖片描述

然后從Arr[L+1]的位置取出值,繼續(xù)向右匹配并排序,將匹配到的值(匹配規(guī)則如下)插入到右側(cè)Arr[R]的空位置上;

匹配規(guī)則:大于基準(zhǔn)值的插入到Arr[R],如果小于,則直接忽略并跳過,繼續(xù)向右取值,直到坐標(biāo)L和坐標(biāo)R重合。

在這里插入圖片描述

發(fā)現(xiàn)取出的值大于Pivot(基準(zhǔn)值),則將其插入到Arr[R]。

在這里插入圖片描述

左邊有坑,從右邊Arr[R-1]繼續(xù)匹配,Arr[R-1] = 1,小于基準(zhǔn)值,則插入到Arr[L]的坑中;

在這里插入圖片描述

右邊有坑了,繼續(xù)從左邊取值繼續(xù)匹配,則取到Arr[L+1] = 9,小于基準(zhǔn)值,則忽略并跳過,繼續(xù)找Arr[L + 1]繼續(xù)匹配。

在這里插入圖片描述

繼續(xù)從左邊坐標(biāo) + 1 取值繼續(xù)匹配,則取到Arr[L] = 17,又小于基準(zhǔn)值,則忽略并跳過,繼續(xù)找Arr[L + 1]繼續(xù)匹配。

在這里插入圖片描述

最后L坐標(biāo)和R坐標(biāo)重合了,將Pivot基準(zhǔn)值填入

在這里插入圖片描述

至此,快速排序第一輪完整流程結(jié)束,分出了左右子序列,左邊都是小于Pivot基準(zhǔn)值的,右邊都是大于Pivot基準(zhǔn)值的。

在這里插入圖片描述

繼續(xù)對左、右子序列遞歸進(jìn)行處理,一直縮小到左、右都是一個值,則快速排序結(jié)束,最終得出順序數(shù)組{1,8,9,17,19,97};中間遞歸流程這里不再贅述。

在這里插入圖片描述

追問3:來吧!給我手敲一個快排

package com.softsec.demo;
/**
 * Created with IDEA
 *
 * @Author Chensj
 * @Date 2020/5/17 19:04
 * @Description
 * @Version 1.0
 */
public class quickSortDemo {
    public static void main(String[] args) {
        // 創(chuàng)建測試數(shù)組
        int[] arr = new int[]{19,97,9,17,1,8};
        System.out.println("排序前:");
        showArray(arr); // 打印數(shù)組
        // 調(diào)用快排接口
        quickSort(arr);
        System.out.println("\n" + "排序后:");
        showArray(arr);// 打印數(shù)組
    }
    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array) {
        int len;
        if(array == null
                || (len = array.length) == 0
                || len == 1) {
            return ;
        }
        sort(array, 0, len - 1);
    }
    /**
     * 快排核心算法,遞歸實(shí)現(xiàn)
     * @param array
     * @param left
     * @param right
     */
    public static void sort(int[] array, int left, int right) {
        if(left > right) {
            return;
        }
        // base中存放基準(zhǔn)數(shù)
        int base = array[left];
        int i = left, j = right;
        while(i != j) {
            // 順序很重要,先從右邊開始往左找,直到找到比base值小的數(shù)
            while(array[j] >= base && i < j) {
                j--;
            }
            // 再從左往右邊找,直到找到比base值大的數(shù)
            while(array[i] <= base && i < j) {
                i++;
            }
            // 上面的循環(huán)結(jié)束表示找到了位置或者(i>=j)了,交換兩個數(shù)在數(shù)組中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
        // 將基準(zhǔn)數(shù)放到中間的位置(基準(zhǔn)數(shù)歸位)
        array[left] = array[i];
        array[i] = base;
        // 遞歸,繼續(xù)向基準(zhǔn)的左右兩邊執(zhí)行和上面同樣的操作
        // i的索引處為上面已確定好的基準(zhǔn)值的位置,無需再處理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }
    /**
     * 數(shù)組打印
     * @param num
     */
    private static void showArray(int[] num) {
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }
}

面試題2:來!再給我手?jǐn)]一個Spring

我:???

追問1:哦,咳咳…說一下構(gòu)成遞歸的前提條件有啥?

函數(shù)內(nèi)部調(diào)用的自身函數(shù)的編程技巧稱為遞歸(recursion)。

構(gòu)成遞歸的條件:

  • 子問題須與原始問題為同樣的事,且更為簡單;
  • 不能無限制地調(diào)用本身,須有個出口,化簡為非遞歸狀況處理。

追問2:遞歸都有哪些優(yōu)缺點(diǎn)?

優(yōu)點(diǎn):

1.簡潔

2.在樹的前序,中序,后序遍歷算法中,遞歸的實(shí)現(xiàn)明顯要比循環(huán)簡單得多。

缺點(diǎn):

1.遞歸由于是函數(shù)調(diào)用自身,而函數(shù)調(diào)用是有時間和空間的消耗的:每一次函數(shù)調(diào)用,都需要在內(nèi)存棧中分配空間以保存參數(shù)、返回地址以及臨時變量,而往棧中壓入數(shù)據(jù)和彈出數(shù)據(jù)都需要時間。(效率)

2.遞歸中很多計算都是重復(fù)的,由于其本質(zhì)是把一個問題分解成兩個或者多個小問題,多個小問題存在相互重疊的部分,則存在重復(fù)計算,如fibonacci斐波那契數(shù)列的遞歸實(shí)現(xiàn)。(效率)

3.調(diào)用??赡軙绯?,其實(shí)每一次函數(shù)調(diào)用會在內(nèi)存棧中分配空間,而每個進(jìn)程的棧的容量是有限的,當(dāng)調(diào)用的層次太多時,就會超出棧的容量,從而導(dǎo)致棧溢出。(性能)

追問3:給我手寫一個簡單的遞歸算法的實(shí)現(xiàn)吧

例如遞歸計算一下n的階乘

package com.softsec;
/**
 * 遞歸計算n的階乘
 * @author Chenhh
 */
public class demo {
    public static void main(String[] args) {
        System.out.println(recursion(5));
    }
    /**
     * 遞歸計算n的階乘
     */
    private static int recursion(int n) {
        if (n <1) {
            throw new IllegalArgumentException("參數(shù)必須大于0");
        } else if (n == 1) {
            return 1;
        } else {
            return n * recursion(n - 1);
        }
    }
}

面試題3: 10億個數(shù)中找出最大的100000個數(shù)(top K問題)

先拿100000個數(shù)建堆,然后一次添加剩余元素,如果大于堆頂?shù)臄?shù)(100000中最小的),將這個數(shù)替換堆頂,并調(diào)整結(jié)構(gòu)使之仍然是一個最小堆,這樣,遍歷完后,堆中的100000個數(shù)就是所需的最大的100000個。建堆時間復(fù)雜度是O(m),算法的時間復(fù)雜度為1次建堆時間+n次堆調(diào)整時間=O(m+nlogm)=O(nlogm)(n為10億,m為100000)。

優(yōu)化的方法:可以把所有10億個數(shù)據(jù)分組存放,比如分別放在1000個文件中。這樣處理就可以分別在每個文件的10^6個數(shù)據(jù)中找出最大的100000個數(shù),合并到一起在再找出最終的結(jié)果。

top K問題

在大規(guī)模數(shù)據(jù)處理中,經(jīng)常會遇到的一類問題:在海量數(shù)據(jù)中找出出現(xiàn)頻率最好的前k個數(shù),或者從海量數(shù)據(jù)中找出最大的前k個數(shù),這類問題通常被稱為top K問題。例如,在搜索引擎中,統(tǒng)計搜索最熱門的10個查詢詞;在歌曲庫中統(tǒng)計下載最高的前10首歌等。

針對top K類問題,通常比較好的方案是分治+Trie樹/hash+小頂堆(就是上面提到的最小堆),即先將數(shù)據(jù)集按照Hash方法分解成多個小數(shù)據(jù)集,然后使用Trie樹活著Hash統(tǒng)計每個小數(shù)據(jù)集中的query詞頻,之后用小頂堆求出每個數(shù)據(jù)集中出現(xiàn)頻率最高的前K個數(shù),最后在所有top K中求出最終的top K。

對于有10億個整數(shù),如何找出其中最大的10萬個這個問題

最容易想到的方法是將數(shù)據(jù)全部排序,然后在排序后的集合中進(jìn)行查找,最快的排序算法的時間復(fù)雜度一般為O(nlogn),如快速排序。但是如果按每個int類型占4個字節(jié),10億個整數(shù)就要占用4G的存儲空間,對于一些java運(yùn)行內(nèi)存小于4G的計算機(jī)而言,直接OOM(out of memory)了。其實(shí)即使內(nèi)存能夠滿足要求(我機(jī)器內(nèi)存都是8GB),該方法也并不高效,因為題目的目的是尋找出最大的100000個數(shù)即可,而排序卻是將所有的元素都排序了,做了很多的無用功。

第二種方法為局部淘汰法,該方法與排序方法類似,用一個容器保存前100000個數(shù),然后將剩余的所有數(shù)字——與容器內(nèi)的最小數(shù)字相比,如果所有后續(xù)的元素都比容器內(nèi)的100000個數(shù)還小,那么容器內(nèi)這個100000個數(shù)就是最大100000個數(shù)。如果某一后續(xù)元素比容器內(nèi)最小數(shù)字大,則刪掉容器內(nèi)最小元素,并將該元素插入容器,最后遍歷完這1億個數(shù),得到的結(jié)果容器中保存的數(shù)即為最終結(jié)果了。此時的時間復(fù)雜度為O(n+m^2),其中m為容器的大小,即100000。

第三種方法是分治法,將10億個數(shù)據(jù)分成1000份,每份100萬個數(shù)據(jù),找到每份數(shù)據(jù)中最大的100000個,最后在剩下的1000 * 100000個數(shù)據(jù)里面找出最大的100000個。如果100萬數(shù)據(jù)選擇足夠理想,那么可以過濾掉1億數(shù)據(jù)里面99%的數(shù)據(jù)。100萬個數(shù)據(jù)里面查找最大的100000個數(shù)據(jù)的方法如下:用快速排序的方法,將數(shù)據(jù)分為2堆,如果大的那堆個數(shù)N大于100000個,繼續(xù)對大堆快速排序一次分成2堆,如果大的那堆個數(shù)N大于100000個,繼續(xù)對大堆快速排序一次分成2堆,如果大堆個數(shù)N小于100000個,就在小的那堆里面快速排序一次,找第100000-n大的數(shù)字;遞歸以上過程,就可以找到第10w大的數(shù)。參考上面的找出第10w大的數(shù)字,就可以類似的方法找到前100000大數(shù)字了。此種方法需要每次的內(nèi)存空間為10^6*4=4MB,一共需要101次這樣的比較。

第四種方法是Hash法。如果這1億個書里面有很多重復(fù)的數(shù),先通過Hash法,把這10億個數(shù)字去重復(fù),這樣如果重復(fù)率很高的話,會減少很大的內(nèi)存用量,從而縮小運(yùn)算空間,然后通過分治法或最小堆法查找最大的100000個數(shù)。

第五種方法采用最小堆。首先讀入前100000個數(shù)來創(chuàng)建大小為100000的最小堆,建堆的時間復(fù)雜度為O(m)(m為數(shù)組的大小即為100000),然后遍歷后續(xù)的數(shù)字,并于堆頂(最?。?shù)字進(jìn)行比較。如果比最小的數(shù)小,則繼續(xù)讀取后續(xù)數(shù)字;如果比堆頂數(shù)字大,則替換堆頂元素并重新調(diào)整堆為最小堆。整個過程直至10億個數(shù)全部遍歷完為止。然后按照中序遍歷的方式輸出當(dāng)前堆中的所有100000個數(shù)字。該算法的時間復(fù)雜度為O(nmlogm),空間復(fù)雜度是100000(常數(shù))。

總結(jié)

本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

最新評論