国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

得到一個數組中任意X個元素的所有組合 即C(n,m)

haoguo / 1398人閱讀

摘要:一個面試題一個數組找出這樣的三個元素它們的和與目標值最接近如原始數組目標值這樣的三個元素算法沒有想到什么好的算法可以快捷的找到這樣的三個元素只想到了窮舉法即找出所有的任意三元素數組長度放到優先隊列中按三個元素的和與目標值的差值絕對值進行排序

一個面試題

一個數組 找出這樣的三個元素 它們的和與目標值最接近

原始數組: [15, 27, 31, 33, 39, 44, 50, 57, 86, 91]
目標值: 98
這樣的三個元素:15,33,50 (15+33+50=98)

算法

沒有想到什么好的算法 可以快捷的找到這樣的三個元素
只想到了窮舉法 即

找出所有的任意三元素 C(數組長度,3)

放到優先隊列中 按三個元素的和與目標值的差值(絕對值)進行排序

第一個即是與目標值最接近的三元素

偽代碼
// 得到所有的三元素組合列表 如["1,2,3", "4,5,6" , ...]
List allUniqueThreeElements = getAllUniqueThreeElements(a,3);

// 三元素列表轉成對象  對象中提供了這樣的方法:getDiff (計算三元素的和與目標值的差值(絕對值))
List threeElementsList = new ArrayList<>();
for (String s : allUniqueThreeElements) {
    elementsList.add(new ThreeElements(s));
}
// 構造優先隊列 按三元素的和與目標值的差值(絕對值)進行排序 優先隊列默認大小為三元素組合列表大小
PriorityQueue pq = new PriorityQueue<>(threeElementsList.size(),comparingInt(o -> o.getDiff(target))); 

// 將三元素組合對象 逐一放到優先隊列中
for (ThreeElements e : threeElementsList) {
    pq.offer(e);
}

ThreeElements poll = pq.poll(); // 優先隊列中 第一個即為要找的三元素
詳細介紹 如何找到一個數組中的所有的X元素組合

即C(n,m)

如 數組 [1,2,3,4,5] 找出所有的元素組合

index 0 1 2 3 4
copy1 1 2 3 4 5
copy2 1 2 3 4 5
copy3 1 2 3 4 5

相當于將同一數組復制三份 每一份中 取一個元素 不重復即可

這樣的取法

copy1 copy2 copy3 -
0 1 2 1,2,3
0 1 3 1,2,4
0 1 4 1,2,5
0 1 5 超過最大索引值 從前一位開始遞增 同時逐個更新后面的值 即后一位的值 = 前一位 + 1
0 2 3 1,3,4
0 2 4 1,3,5
0 2 5 超過最大索引值 從前一位開始遞增
0 3 4 1,4,5
0 3 5 超過最大索引值 從前一位開始遞增
0 4 5 超過最大索引值 從更一位開始遞增
1 2 3 2,3,4
1 2 4 2,3,5
1 2 5 超過最大索引值 從前一位開始遞增
1 3 4 2,4,5
1 3 5 超過最大索引值 從前一位開始遞增
1 4 5 超過最大索引值 從更一位開始遞增
2 3 4 3,4,5
2 3 5 超過最大索引值 從前一位開始遞增
2 4 5 超過最大索引值 從更一位開始遞增
3 4 5 超過最大索引值 且此時不存在更前一位了 退出
對應的代碼
    /**
     * 
     * @param indexArray 索引數組
     * @param maxIndexValue 最大索引值
     * @param startIndex indexArray中從此位開始遞增
     * @return
     */
    private boolean next(final int[] indexArray, final int maxIndexValue, int startIndex){
//        System.out.println("indexArray: "+Arrays.toString(indexArray));
//        System.out.println("startIndex: "+startIndex);
        indexArray[startIndex]++; // 從此位開始遞增
        if(indexArray[startIndex] > maxIndexValue){ // 超過最大索引值 從前一位開始遞增
            return next(indexArray,maxIndexValue,startIndex-1);
        }else{
            // 同時逐個累加之后的元素 后一位的值 = 前一位+1
            for (int i = startIndex+1; i < indexArray.length; i++) {
                indexArray[i] = indexArray[i-1]+1;
                if(indexArray[i] > maxIndexValue){
                    if(startIndex -1 < 0){ // 如果是從第一位開始遞增的 即不存在更前一位了 則退出遞歸
                        return false;
                    }
                    return next(indexArray,maxIndexValue,startIndex-1);
                }
            }
            return true;
        }
    }

測試代碼

    @Test
    public void test_next(){
        // 測試從一個數組中得到所有的三元素組合
        int[] a = {1, 2, 3, 4, 5}; // 數組
        int maxIndexValue = a.length-1; // 最大索引值
        int[] indexArray = {0,1,2}; // 初始化索引數組
        int startIndex = indexArray.length-1; // 從末位開始遞增

        // 驗證  [0,1,2] --> [0,1,3]
        boolean next = next(indexArray, maxIndexValue, startIndex);
        assertTrue(next);
        assertArrayEquals(new int[]{0,1,3}, indexArray);

        // 驗證 [0,1,4] --> [0,2,3]
        indexArray = new int[]{0, 1, 4};
        next = next(indexArray, maxIndexValue, startIndex);
        assertTrue(next);
        assertArrayEquals(new int[]{0,2,3}, indexArray);

        // 驗證 [0,3,4] --> [1,2,3]
        indexArray = new int[]{0, 3, 4};
        next = next(indexArray, maxIndexValue, startIndex);
        assertTrue(next);
        assertArrayEquals(new int[]{1,2,3}, indexArray);

        // 驗證 [2,3,4] --> X
        indexArray = new int[]{2, 3, 4};
        next = next(indexArray, maxIndexValue, startIndex);
        assertFalse(next);
    }

當驗證其他一些極端情況的時候 如從一個數組中得到所有一個元素的組合 即C(n,1) 測試沒有通過

    @Test
    public void test_next_and_only_choose_one_element(){
        // 測試一些更極端的情況 如 一個數組中選出所有1個元素的組合(C(n,1))
        final int[] a = {1, 2, 3, 4, 5};
        int maxIndexValue = a.length-1;
        int[] indexArray = {0};
        int startIndex = indexArray.length-1;


        //驗證 [0] -> [1]
        boolean next = next(indexArray, maxIndexValue, startIndex);
        assertTrue(next);
        assertArrayEquals(new int[]{1},indexArray);
        System.out.println();
        // 驗證 [4] -> X
        indexArray = new int[]{4};
        next = next(indexArray, maxIndexValue, startIndex);
        assertFalse(next);
    }

修復代碼 將判斷最后沒有下一組的代碼給提取出來了

    private boolean next(final int[] indexArray, final int maxIndexValue, int startIndex){
        if(startIndex < 0){ // 如果不存在更前一位了 則退出遞歸
            return false;
        }
        indexArray[startIndex]++; // 從此位開始遞增
        if(indexArray[startIndex] > maxIndexValue){ // 超過最大索引值 從前一位開始遞增
            return next(indexArray,maxIndexValue,startIndex-1);
        }else{
            // 同時逐個累加之后的元素 后一位的值 = 前一位+1
            for (int i = startIndex+1; i < indexArray.length; i++) {
                indexArray[i] = indexArray[i-1]+1;
                if(indexArray[i] > maxIndexValue){
                    return next(indexArray,maxIndexValue,startIndex-1);
                }
            }
            return true;
        }
    }
參考文檔

http://wiki.jikexueyuan.com/p...

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66647.html

相關文章

  • javasm>cm>ript 最長公共子序列

    摘要:但不是和的最長公共子序列,而序列和也均為和的最長公共子序列,長度為,而和不存在長度大于等于的公共子序列。最長公共子序列給定序列和,從它們的所有公共子序列中選出長度最長的那一個或幾個。為和的最長公共子序列長度。 最長公共子序列(Longest Common Subsequence LCS)是從給定的兩個序列X和Y中取出盡可能多的一部分字符,按照它們在原序列排列的先后次序排列得到。LCS問...

    Xufc 評論0 收藏0
  • Pythom>nm>學習之路21-序列構成數組

    摘要:第行把具名元組以的形式返回。對序列使用和通常號兩側的序列由相同類型的數據所構成當然不同類型的也可以相加,返回一個新序列。從上面的結果可以看出,它雖拋出了異常,但仍完成了操作查看字節碼并不難,而且它對我們了解代碼背后的運行機制很有幫助。 《流暢的Python》筆記。接下來的三篇都是關于Python的數據結構,本篇主要是Python中的各序列類型 1. 內置序列類型概覽 Python標準庫...

    ralap 評論0 收藏0
  • 由三道 Leetm>Cm>ode 題目簡單了解一下位運算

    摘要:使用位運算數組只出現一次數字的數組得到最低的有效位,即兩個數不同的那一位看完上面的解法,我腦海中只有問號的存在,啥意思啊下面就讓我們簡單了解一下位運算并解析一下這三道題目。另,負數按補碼形式參加按位與運算。你可做過這幾道題? 在面試的準備過程中,刷算法題算是必修課,當然我也不例外。某天,我刷到了一道神奇的題目: # 136. 只出現一次的數字 給定一個非空整數數組,除了某個元素只出現一次以外...

    daydream 評論0 收藏0

發表評論

0條評論

haoguo

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<