小弟今天在實(shí)驗(yàn)室遇到校外有人來面試我們實(shí)驗(yàn)室的人，其中最后個(gè)就是編寫一個(gè)函數(shù)返回?cái)?shù)組中第三個(gè)最大數(shù)的下標(biāo)。我最先想到的就是先排序，再取第三個(gè)最大數(shù)，最后將取得的第三個(gè)最大數(shù)再在原數(shù)組中遍歷獲取下標(biāo)，然而這樣的效率并不高。最后經(jīng)面試官點(diǎn)撥了下，想到“排擠”的思想，即默認(rèn)已有三個(gè)排序好的最大數(shù) a[k] < a[m] < a[n]，再在數(shù)組中遍歷與這三個(gè)數(shù)做比較，滿足條件則交換相應(yīng)的下標(biāo)，擠出原數(shù)據(jù)，永遠(yuǎn)保證這三個(gè)數(shù)在已遍歷的數(shù)中最大，最后再返回下標(biāo) k 。這樣做時(shí)間復(fù)雜度只有 O(n)，具體代碼見下：

import java.lang.reflect.Array;

public class Test1 {
    /*
     * 利用“排擠”的思想
     */
    public static int findThirdM(int a[]){
        int b[];
        int k = 0;
        int m = 1;
        int n = 2;
        for(int i=0; i<a.length ; i++){
            // 先判斷a[i]是否大于第三個(gè)最大數(shù)
            if (a[i] >= a[k]) {
                // 在判斷a[i]是否大于第二個(gè)最大數(shù)
                if (a[i] >= a[m]) {
                    // 最后判斷a[i]是否大于第一個(gè)最大數(shù)
                    if (a[i] >= a[n]) {
                        // 交換相應(yīng)的下標(biāo)
                        k = m; // 當(dāng)滿足第一個(gè)最大數(shù)時(shí)不要忘記先交換后兩個(gè)最大數(shù)的坐標(biāo)
                        m = n;
                        n = i;
                    }else {
                        k = m;
                        m = i;
                    }
                }else{
                    k = i;
                }
            }
        }
        return k;
    }
     /*
     * 先排序，再取下標(biāo)的方法，復(fù)雜度大于O(n)
     */
    public static int findByBubble(int[] a) {
        // 先將數(shù)組存儲(chǔ)在另一個(gè)數(shù)組中
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i];
        }
        //利用冒泡排序找出最大的三個(gè)數(shù)，從大到下排序，
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < a.length-1; j++) {
                if (a[j] < a[j+1]) {
                    a[j] = a[j+1];
                }
            }
        }
        //經(jīng)上步驟獲得的第三個(gè)最大數(shù)a[2]，再數(shù)組b中遍歷取下標(biāo)
        for (int i = 0; i < b.length; i++) {
            if (a[2] == b[i]) {
                return i;
            }
        }
        return 0;
    }        

    public static void main(String[] args) {
        int[] arr = {0,1,11,9,10,5,13,7,1,15};
        System.out.println("第三個(gè)最大數(shù)的下標(biāo)為："+findThirdM(arr));
        System.out.println(findByBubble(arr));
    }
}