We Learn   We Create   We Share

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

目录

AtCoder C 212

AtCoder

Leon | 01 Aug 2021

题目描述

有两个数组分别是有N个整数的A数组和有M个整数的B数组，求两个数组中最小的整数差。

题目思路

题目本质上是要求两个书数组中最接近的两个数。

方法一：暴力枚举

将一个数组中的所有数与另外一个数组中的所有数进行相减，然后取最小值。

那么此时的总体复杂度为 \(O(N^2)\) 但是 \(1\le N,M\le 2\times 10^5\) 所以这一种情况肯定会TLE。

方法二：双指针

将两个数组分别排序

排序之后分别放置两个指针在两个数组的开头，不停的重复以下操作：

若 \(A[pointerA]\le B[pointerB]\) 则pointerA+1，反之则pointerB+1。并记录最小的差值。

复杂度分析：

数组排序： \(O(n\log n)\) 双指针遍历数组： \(O(n)\) 所以总体复杂度为 \(O(n\log n)\)

代码实现

import java.util.*;
public class min{
    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 i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        for (int i = 0; i < b.length; i++) {
            b[i] =in.nextInt();
        }
        Arrays.sort(a);
        Arrays.sort(b);
        int pointGuardA = 0;
        int pointGuardAB = 0;
        int min = (int)Math.abs(a[0]-b[0]);
        
        while(pointGuardA!=n&&pointGuardAB!=m){
            min = Math.min(min, (int)Math.abs(a[pointGuardA]-b[pointGuardAB]));
            if(min==0) break;
            if(a[pointGuardA]>b[pointGuardAB]) pointGuardAB++;
            else pointGuardA++;
        }
        System.out.println(min);
    }
}

评论区