题解 | #奶牛排队问题#

题目考察的知识点

考察哈希算法的应用

题目解答方法的文字分析

对于本题，构建哈希表用于存储（体重：所在位置的序列），随后遍历，检查有同一体重下有多个位置的集合中是否有满足位置间距小于k的存在，如果存在就返回true。具体细节参看代码注释即可。

本题解析所用的编程语言

使用Java语言解答

完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型一维数组 
     * @param n int整型 
     * @param k int整型 
     * @return bool布尔型
     */
    public boolean checkDuplicate (int[] weights, int n, int k) {
        // write code here
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>(); // 体重：所在位置的序列
        for(int i=0; i<n; i++){
            if(map.containsKey(weights[i])){
                ArrayList<Integer> l = map.get(weights[i]);
                l.add(i); //记录位置
            }else{
                ArrayList<Integer> l = new ArrayList<>();
                l.add(i);
                map.put(weights[i],l);
            }
        }
        for(int num:map.keySet()){
            if(map.get(num).size()<=1) continue;
            else{ //存在多个相同体重的牛
                ArrayList<Integer> temp = map.get(num);
                int len = temp.size();
                for(int i=1; i<len; i++){
                    if(temp.get(i)-temp.get(i-1)<=k) return true; //存在争抢的情况
                }
            }
        }
        return false;
    }
}