We Learn   We Create   We Share

初学者指南
笔记
竞赛
关于我们
页面搜索

目录

AtCoder C 212

AtCoder

djw | 05 Aug 2021

题目大意

题目会给两组数 A, B. 长度分别为 N, M. 要找到两组数中最小的差 \(1\leqslant N,M \leqslant 2 \times 10^5 \\1 \leqslant A_i \leqslant 10^9 \\1 \leqslant B_i \leqslant 10^9\)

解题思路

从数据大小可以看出，直接暴力枚举会超时–O(n^2)

可以先把两组数据排序 ： B(n+1)>Bn , A(n+1)>An

​ 排序 ：复杂度：O(nlogn)

如果当Bn>A时，Bn-An 会比 Bn-A(n+1) 差的多 所以直接看A(n+1)

当An>B时，同理 可以直接看B(n+1)

​ 遍历一遍： 复杂度：O(n)

总的复杂度–O(nlogn)

代码

import java.util.*;
public class minDifference {
    public static void main (String[] args) {
        Scanner in = new Scanner (System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[] a = new int[N];
        int[] b = new int[M];
        for(int n = 0; n < N; n++) a[n] = in.nextInt();
        for(int m = 0; m < M; m++) b[m] = in.nextInt();
        
        Arrays.sort(a);
        Arrays.sort(b);
        int ans =Integer.MAX_VALUE;

        int i = 0;
        int j = 0;
        while(i < N && j < M) {
            ans = Math.min(ans, Math.abs(a[i]-b[j]));
            if(a[i]<b[j]) i++;
            else j++;
        }
        System.out.println(ans);
    }
}

评论区