雨林OA过经顺便讨论一下prime air解法

第一题是刷题网酒伞其的变种。
第二题是prime air，我大部分test case都

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

41 +8:00):
还有求米看面经！谢谢！

双指针的话应该是要loop 两遍， 但是还是要考虑去重的问题
比如 第一遍 A 指针从0 开始， B 指针从末尾开始
第二遍 A 指针从 末尾开始， B 指针从0开始。 这个解法我也没有非常确定，但想不出反例。

最好的解法还是用map，可以参考这个老哥的代码，这是在刷题网discuss下面的答案，coding style不好，但是思路肯定是对的

1. public static void main(String[] args) {
   
2.     int arr1[][] = { {1, 2000}, {2, 3000}, {3, 4000}, {4, 2000} };
   
3.     int arr2[][] = { { 1, 5000 }, {2, 3000} };
   
4. 
   
5.    List<int[]> re = getClosestPairs(arr1, arr2, 7500);
   
6. 
   
7.    for(int[] r : re)
   
8.    {
   
9.        System.out.println(r[0] + " " + r[1]);
   
10.    }
    
11. }
    
12. 
    
13. 
    
14. private  static  List<int[]> getClosestPairs(int[][] A, int[][] B, int target)
    
15. {
    
16. 
    
17.     TreeMap<Integer, List<Integer>> valueWithIds = new TreeMap<>();
    
18. 
    
19.     List<int[]> result = new ArrayList<>();
    
20. 
    
21.     int closestTarget = 0;
    
22. 
    
23.   /*
    
24.        Loop through the first Array and insert the values into the map with 'value' (A[1]) as key and id (A[0]) add to the list as value.
    
25.   */
    
26. 
    
27.     for(int[] a  : A)
    
28.     {
    
29.         int currentTarget = a[1], id = a[0];
    
30.         valueWithIds.putIfAbsent(currentTarget, new ArrayList<>());
    
31.         valueWithIds.get(currentTarget).add(id);
    
32. 
    
33.     }
    
34. 
    
35. 
    
36.     for(int[] b : B)
    
37.     {
    
38.         int remainingTarget = target - b[1];  // We will find the remaining target by the value from the value of B.
    
39.       // For example if target = 5000, b[1] = 3000, then remainingTarget = 2000
    
40. 
    
41.         if(remainingTarget < 0) continue;
    
42. 
    
43.         if(valueWithIds.containsKey(remainingTarget)) // That means we find the closest target == currentTarget
    
44.         {
    
45.              if(closestTarget != target)
    
46.              {
    
47.                  closestTarget = target;
    
48.                  result = new ArrayList<>();
    
49.              }
    
50. 
    
51.              for(int id : valueWithIds.get(remainingTarget) )
    
52.              {
    
53. 
    
54.                  result.add(new int[] {id, b[0]});
    
55.              }
    
56. 
    
57.         }
    
58. 
    
59.         else
    
60.         {
    
61.             Integer floor = valueWithIds.floorKey(remainingTarget);  // Check if we have any least value which is less than remainingTarget.
    
62. 
    
63.             if(floor == null) continue;
    
64. 
    
65.             int currentTarget = b[1] + floor;
    
66. 
    
67.             if(  currentTarget >= closestTarget )
    
68.             {
    
69.                 if(currentTarget != closestTarget)
    
70.                 {
    
71.                     closestTarget = currentTarget;
    
72.                     result = new ArrayList<>();
    
73.                 }
    
74. 
    
75.                 for(int id : valueWithIds.get(floor) )
    
76.                 {
    
77.                     result.add(new int[] {id, b[0]});
    
78.                 }
    
79.             }
    
80. 
    
81.         }
    
82.     }
    
83. 
    
84. 
    
85.     return result;
    
86. }}

复制代码

谢谢楼主分享