时间戳

首页 > 技术文章 > 编程练习-快速寻找满足条件的两个数

编程练习-快速寻找满足条件的两个数

numen-fan 2019-03-07 20:45 原文

题目-来自编程之美

给定一个数组，快速从其中找出两个数满足其之和等于给定的数，这里假设其中至少存在一组符合要求的解；

分析

这里的关键在于快速

  • 最为愚钝的方式当然是：穷举，从数组中任意取出两个数字进行判断，但是时间复杂度为$O(N^2)$;
  • 一般是数组，首先进行排序，采用时间复杂度为$O(Nlog_2N)$, 然后通过一次遍历求出所需的解，时间复杂度为$O(N)$， 所以整个时间复杂度为$O(Nlog_2N)$，
    • 书中分析： 令i = 0, j = n - 1, 查看arr[i] + arr[j]是否等于sum，如果是则结束，否则判断大小，如果小于sum，则i++,否则j--, 这样从两端向中间移动，则一定会找到的。
    • 同时我借助快排思想中移动，上面每次只移动一个位置，能不能一次移动多个，这样在两个目标数距离比较近时，能过更加快速的找到。详见代码！事实证明可行！

实现(java)


package com.jiajia.find;

/**
 * @ClassName: FindTowNum
 * @Author: fanjiajia
 * @Date: 2019/3/7 下午7:28
 * @Version: 1.0
 * @Description: 在一个序列中快速查找两个满足条件的两个数
 */
public class FindTowNum {

    public static void main(String[] args) {

        int[] arr = {2,3,9,5,7,8,4,6};

        function(arr, 14);

    }

    private static void function(int[] arr, int targetNum) {
        // 先排序（从小到大）
        quickSort(arr, 0, arr.length - 1);
        // 方法1：每次只移动一个下标
        boolean flag = false;   // 方法1是否寻找到
        for (int i = 0, j = arr.length - 1; i < j; ){
            if (arr[i] + arr[j] == targetNum){
                System.out.println("方法1->存在两个数，分别为:" + arr[i] + "," + arr[j]);
                flag = true;
                break;
            }else if (arr[i] + arr[j] < targetNum){
                i++;
            }else {
                j--;
            }
        }
        if (!flag){
            System.out.println("不存在");
        }

        // 方法2
        int i = 0, j = arr.length - 1;
        while (i < j && (arr[i] + arr[j] != targetNum)) { // i 和 j不可能重合
            while (arr[i] + arr[j] < targetNum && i < j) { // 移动i
                i++;
            }
            while (arr[i] + arr[j] > targetNum && i < j) { // 移动j
                j--;
            }
        }
        if (i < j){
            System.out.println("方法2->存在两个数，分别为:" + arr[i] + "," + arr[j]);
        }else {
            System.out.println("不存在");
        }
    }

    /**
     * 快排
     * @param arr
     * @param left
     * @param right
     */
    private static  void quickSort(int[] arr, int left, int right){

        if (left >= right) {    // 必须加
            return;
        }

        int temp = arr[left]; // 以左边的元素为基准元素
        int i = left, j = right; // i,j为两个游标
        while (i < j) {
            while (i < j && arr[j] >= temp){ // 右边先走
                j--;
            }
            while (i < j && arr[i] <= temp) {
                i++;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        arr[left] = arr[i]; // 注意，这一步必须要，填上最左边的坑
        arr[i] = temp; // 基准元素就位
        quickSort(arr, left, i - 1);    // 递归操作左边部分
        quickSort(arr, i + 1, right);   // 递归操作右边部分
    }

    /**
     * 交换两个元素
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

最后

此致，敬礼！

推荐阅读