Java容器使用：Map

1.题目说明

2.思路分析

题目的意思也就是说，要在数组第 j 个元素前的几个元素里找到与其差的绝对值最小的元素，返回其差值以及下标。

那显然，差的绝对值最小无非两种情况，一个是大于该元素的最小元素，一个是小于该元素的最大元素，那我们很自然的就想到TreeMap里的两个函数：ceilingEntry（key）和floorEntry（key）。他们分别可以返回大于等于key的最小元素以及小于等于key的最大元素。

那么，最小差值就是（key - 小于等于key的最大元素），或者是（大于等于key的最小元素 - key）

具体取哪个值需要比较一下，谁更小就取谁，而位置则是存在了TreeMap的value里，直接调用getValue（）即可。

3.代码实现

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
 
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        TreeMap x = new TreeMap<>();
        int n = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n;i++)
            a[i] = in.nextInt();
        x.put(a[0],0);//map里不能没有东西，因为需要比较，相当于初始化。
        for(int i = 1;i < n;i++){
            Map.Entry up = x.ceilingEntry(a[i]);
            Map.Entry down = x.floorEntry(a[i]);//注意：map的对象类型是map.entry。
            int pos = -1,minus = Integer.MAX_VALUE;//把minus设成极大是因为防止在up为null时，minus过小而导致第二个if直接为false
            if(up != null){
                minus = up.getKey() - a[i];
                pos = up.getValue();
            }
            if(down != null && (a[i] - down.getKey() <= minus)){
               minus = a[i] - down.getKey();
               pos = down.getValue();
            }//判定条件里要与minus作比较，可能是初始设定的极大值，也有可能是up不等于null判定完算出来的up.getkey() - a[i].
            System.out.println(minus + " " + (pos + 1));
            x.put(a[i] , i);//需要将这一对加到map里进行后续的操作。
        }
    }
 
}

虽然题简单，但涉及到的一些细节需要好好考虑，如将minus的初值设定为int型所能存的最大数值。

4.对于Map的理解

Map存的是一个二元组，可以理解成数学上的映射，即每个key都对应一个value。那它所能处理的东西就不是简简单单的一个数据了。它存的是数据以及数据之间的关系。最经典的例子莫过于这道题里的数组元素及其下标，原来做的题里还有目标数字在数组中出现的次数，也可以用Map来存。

Map更偏向于存的是一对有关系的数据。

5.Map里的一些常用函数

接口：java.util.Map
 
实现：
 
java.util.HashMap：哈希表
java.util.TreeMap：平衡树
函数：
 
put(key, value)：添加关键字和其对应的值
get(key)：返回关键字对应的值
containsKey(key)：是否包含关键字
remove(key)：删除关键字
size()：返回元素数
isEmpty()：是否为空
clear()：清空
entrySet()：获取Map中的所有对象的集合
Map.Entry：Map中的对象类型
getKey()：获取关键字
getValue()：获取值
java.util.TreeMap多的函数：
 
ceilingEntry(key)：返回大于等于key的最小元素，不存在则返回null
floorEntry(key)：返回小于等于key的最大元素，不存在则返回null