lincode 最佳利用率

Posted on | In

描述

给两个排序的数组。 从两个数组中各取取一个数，这两个数之和需要小于或等于k， 需要找到两数之和最大的索引组合。返回一对包含两个列表的索引。如果有多个两数之和相等的索引答案，你应该选择第一个数组索引最小的索引对。
1）两数的总和<= k
2）总和是最大的
3）两个数组索引都尽量最小

样例

1

输入:
A = [1, 4, 6, 9], B = [1, 2, 3, 4], K = 9
输出:
[2, 2]

2

输入:
A = [1, 4, 6, 8], B = [1, 2, 3, 5], K = 12
输出:
[2, 3]

思路

遍历A中每个数，在B中做二分检索，找最接近的数
注意更新的时候的细节

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    /**
     * @param A: a integer sorted array
     * @param B: a integer sorted array
     * @param K: a integer
     * @return: return a pair of index
     */
    vector<int> optimalUtilization(vector<int> &A, vector<int> &B, int K) {
        // write your code here

        if (A.size() == 0 || B.size() == 0)
            return vector<int>(0,0);

        int distance = INT_MAX;
        vector<int> res(2,0);
        for (int i = 0; i < A.size(); i++) {
            int a = A[i];
            int target = K-a;

            int Max = B.size()-1, Min = 0, Mid = 0;

            while (Min <= Max) {

                Mid = (Max+Min)/2;

                if (B[Mid] == target) {
                    res[0] = i;
                    res[1] = Mid;
                    return res;
                }

                else if (B[Mid] > target) {
                    Max = Mid-1;
                }
                else {
                    Min = Mid+1;
                }

                if (K - A[i] - B[Mid] < distance && K - A[i] - B[Mid] > 0) {
                    res[0] = i;
                    res[1] = Mid;
                    distance = K - ( A[i] + B[Mid] );
                }
            }
        }
        return res;

    }
};
-------------end of filethanks for reading-------------