题目描述

题目解析

暴力

优化

先对数组排序，然后：

• 答案可能来自所有的负数区【显然是最大的俩负数的和的绝对值】，比如-1-2绝对值为3
• 答案可能来自所有的非负数区【显然是最小的俩整数的和的绝对值】，比如0+1=1
• 答案可能同时来自负数区，可能来自非负数区，-1+0=1。因此，我们遇到一个负数x，需要找非负数区的最接近于|x|的的那个数

#include<bits/stdc++.h>
using namespace std;

int mostApproach(std::vector<int>arr, int L, int R, int k){
    if (L > R) return -1;
    if (L == R) return arr[L];

    //R>L
    int j = L;
    while (L <= R){
        int mid = L + ((R - L) >> 1);
        if (arr[mid] <= k) {
            j = mid;//先记下它
            L = mid + 1;//继续往右找，看看能否找到==k的
        }else {
            //arr[mid] > k，过大，需要往左找
            R = mid - 1;
        }
    }
    //如果没有找到，说明全部都大于k呗，那最接近k的只能是L位置了
    if (j == R) return j;
    else return k - arr[j] <= k - arr[j + 1] ? j : j + 1;
    //返回的是最接近的，可能j+1会更接近哦
}


int minAbsoluteValueOfTwoNum(std::vector<int>arr){
    if(arr.empty() || arr.size() < 2){
        return 0;
    }

    std::sort(arr.begin(), arr.end());

    int N = arr.size();
    int min = 0;
    int j0 = mostApproach(arr, 0, N - 1, 0);//找到0处的位置
    //看看0左边有几个负数？
    if(j0 == 0){  // 要求绝对值最小
        return arr[1]; // 没有负数： 0 + arr[1]
    }else if(j0 == 1){  // 只有一个负数
        min = abs(arr[0]);
    }else{
        min = abs(arr[j0 - 1] + arr[j0 - 2]); // 超过两个负数
    }

    //然后遍历负数区,找0--N-1上最接近x的那个位置j
    for (int i = 0; i < j0; ++i) {
        int j = mostApproach(arr, j0, N - 1, abs(arr[i]));
        min = std::min(min, abs(arr[i] + arr[j]));
    }
    return min;
}

最后

以上就是昏睡高山为你收集整理的华为机试：乱序整数序列两数之和绝对值最小题目描述题目解析的全部内容，希望文章能够帮你解决华为机试：乱序整数序列两数之和绝对值最小题目描述题目解析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。