算法之数组和问题

算法题之数组和求解

数组和问题

​ 加上给定一个数组和值x。设计一个算法使得如果数组中存在两个元素的和为x,则输出两个元素的值组成的数组(不区分先后),否则输出{-1, -1}。

​ 分析:

  1. 最简单的办法,就是依次求每个元素与其他元素的和。这个就是经典的握手问题,不难得出其最坏时间复杂度为: \(\Theta\)(\(n^2\)) 这种指数级别的时间复杂度必然不是我们想要的,直接PASS
  2. 先做排序然后再进行查找: 假设使用前面已知的最快的排序算法,最坏时间复杂度为: \(\Theta\)(nlg(n))。之后可以使用二分查找法对每个针对每个元素查找 x - arr[i] 是否在数组中,此时时间最坏时间复杂度为: \(\Theta\)(nlg(n))。该算法实现的代码如下:
private static int[] findSum(int[] arr, int sum) {
        // STEP1: 先对数组采用归并排序进行排序
        mergeSort(arr, 0, arr.length);
        
        // STEP2: 遍历数组,用二分查找法查找是否存在sum-arr[i]的元素
        for (int i=0; i<arr.length; i++) {
            int j = binarySearch(arr, 0, arr.length, sum - arr[i]);
            if (j != -1) {
                if (j != i) {
                    return new int[] {arr[i], arr[j]};
                } else {
                    // j = i的时候,则需要判断j的左侧和右侧的值是否和j相等,相等则证明存在两个元素
                    if (arr[j - 1] == arr[j]) {
                        return new int[] {arr[i], arr[j - 1]};
                    } else if (arr[j + 1] == arr[j]) {
                        return new int[] {arr[i], arr[j + 1]};
                    }
                }
            }
        }
        
        return new int[]{-1, -1};
    }

注意其中的mergeSort和binarySearch调用的是前一章节所指的代码http://www.cnblogs.com/Kidezyq/p/8379267.html


扩展

  • 其实对于求两个元素的和有一种时间复杂度为:\(\Theta\)(n)的算法。该算法利用了桶排序的思想,借助Map的特殊数据结构。我们这里以arr[i]为key,i为value。要判断sum-arr[i]是否存在数组中,只要看map.get(sum-arr[i])是否为空即可。实现的代码如下:
private static int[] findSumWithMap(int[] arr, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        // STEP1: 将数据入map
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], i);
        }

        // STEP2: 开始判断sum-arr[i]是否在map中 
        for (int i = 0; i < arr.length; i++) {
            // 因为遍历顺序同放入map的顺序都是从前到后,所以如果存在多个同值元素,其最终会将后者的下标放入map,此时不影响判断逻辑
            if (map.get(sum - arr[i]) != null && i != map.get(sum - arr[i])) {
                return new int[]{arr[i], sum - arr[i]};
            }
        }
        return new int[]{-1, -1};
    }
  • 其实对于上面的分析方法2,还有一个优化的方法,可以对排序后的数组在时间:\(\Theta\)(n)之内找到两个和为指定值的算法。方法的思想还是二分查找法。首先取两个下边lowIndex和upIndex,最开始的时候lowIndex指向数组首元素,upIndex指向数组末尾元素。然后比对arr[lowIndex] + arr[upIndex]与sum的关系。根据比对的结果分别对lowIndex和upIdex进行移动。此时对于后续的整个查找过程只需要\(\Theta\)(n)时间即可。源代码如下:
private static int[] findSumTwoSide(int[] arr, int sum) {
        // STEP1: 使用归并排序对数组进行排序
        mergeSort(arr, 0, arr.length);
        
        // STEP2: 进行两端查找
        int lowIndex = 0;
        int upIndex = arr.length - 1;
        while (upIndex > lowIndex) {
            if (arr[lowIndex] + arr[upIndex] == sum) {
                // 相等直接返回
                return new int[] {arr[lowIndex], arr[upIndex]};
            } else if (arr[lowIndex] + arr[upIndex] < sum) {
                // 小于左侧右移
                lowIndex++;
            } else {
                // 大于右侧左移
                upIndex--;
            }
        }
        return new int[] {-1, -1};
    }
  • 该题可以延伸至n个元素的和:

其解决思想就是分治了。将n个元素的规模依次降低,最终降到2个元素的和。这里给出三个元素求和的例子,其他多维依次类推:

private static int[] findSumOf3Digits(int[] arr, int sum) {
        // STEP1:先调用归并排序算法进行排序
        mergeSort(arr, 0, arr.length);
        
        // STEP2: 进行细化问题处理
        // 先申请一个数组来存储排除一个元素后的数组元素组成的新的数组
        int[] leftArr = new int[arr.length - 1];    
        for (int i = 0; i < arr.length; i++) {
            // 复制arr[i]左侧元素到数组起始位置
            if (i > 0) {
                System.arraycopy(arr, 0, leftArr, 0, i);
            }
            
            // 复制arr[i]右侧元素到数组结尾位置
            if (i < arr.length - 1) {
                System.arraycopy(arr, i + 1, leftArr, i, arr.length - i - 1);
            }
            
            // 如果剩下两个数的和满足,则返回三个元素
            int[] leftIndexes = findSumTwoSide(leftArr, sum - arr[i]);
            if (!Arrays.equals(leftIndexes, new int[] {-1, -1})) {
                return new int[] {arr[i], leftIndexes[0], leftIndexes[1]};
            }
        }
        
        return new int[] {-1, -1, -1};
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏李蔚蓬的专栏

第12周Python学习周记

>>> b = a                                #没有创建新的对象

1052
来自专栏小樱的经验随笔

Gym 100952G&&2015 HIAST Collegiate Programming Contest G. The jar of divisors【简单博弈】

G. The jar of divisors time limit per test:2 seconds memory limit per test:64 me...

2745
来自专栏测试开发架构之路

程序员面试50题(2)—二元查找树的后序遍历结果[数据结构]

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一...

2636
来自专栏章鱼的慢慢技术路

蓝桥杯题库基础练习:进制转换

1894
来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

3334
来自专栏前端儿

ASCII码排序

输入第一行输入一个数N,表示有N组测试数据。后面的N行输入多组数据,每组输入数据都是占一行,有三个字符组成,之间无空格。输出对于每组输入数据,输出一行,字符中间...

1732
来自专栏机器学习入门

LWC 62:743. Network Delay Time

LWC 62:743. Network Delay Time 传送门:743. Network Delay Time Problem: There are N...

2288
来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

1544
来自专栏有趣的Python

玩转算法面试:(三)LeetCode数组类问题

数组中的问题其实最常见。 排序:选择排序;插入排序;归并排序;快速排序 查找:二分查找法 数据结构:栈;队列;堆 …… 如何写出正确的程序 建立一个基...

5794
来自专栏Python爬虫实战

numpy基础操作快速入门

由于numpy不是python自带库,需要自己下载安装(如果用的是Anaconda,则不需要再去下载numpy库,因为其自带python环境以及许多第三方pyt...

651

扫码关注云+社区