转载

得到一个数组中任意X个元素的所有组合即C(n,m)

一个面试题

一个数组找出这样的三个元素它们的和与目标值最接近

如

原始数组： [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<String> allUniqueThreeElements = getAllUniqueThreeElements(a,3);

// 三元素列表转成对象  对象中提供了这样的方法：getDiff (计算三元素的和与目标值的差值（绝对值）)
List<ThreeElements> threeElementsList = new ArrayList<>();
for (String s : allUniqueThreeElements) {
    elementsList.add(new ThreeElements(s));
}
// 构造优先队列 按三元素的和与目标值的差值（绝对值）进行排序 优先队列默认大小为三元素组合列表大小
PriorityQueue<Elements> 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;
        }
    }

原文 https://segmentfault.com/a/1190000008324538

正文到此结束