Codeforces Round #312 (Div. 2) B. Amr and The Large Array

原题:http://codeforces.com/problemset/problem/558/B

---

题目大意: 给一个数组, 找出其中的子数组,并且要求原数组中出现最多次数的数字在在子数组中.最多次数的数字可以不唯一. 所以答案也不一定唯一

---

分析: 暴啊暴啊…先按照频率排序,然后找同频率下所有的数字间隔在原数组中间隔最小的.

 public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int nums[] = IOUtils.readIntArray(in, n);
        HashMap<Integer,Item> map = new HashMap<>(); // <num, item>
        for (int i = 0 ; i < nums.length; i++) {
            int x = nums[i];
            if (!map.containsKey(x))
                map.put(x,new Item(i,i,1));
            else {
                Item item = map.get(x);
                item.frequency++;
                item.end = i;
                map.put(x, item);
            }
        }
        ArrayList<Pair<Integer,IntPair>> list = new ArrayList<>(); // <freq, <start,end>>
        Iterator<Map.Entry<Integer, Item>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, Item> next = iterator.next();
            list.add(Pair.makePair(next.getValue().frequency, new IntPair(next.getValue().start, next.getValue().end)));
        }
        Collections.sort(list);
        int max = list.get(list.size()-1).first;
        int index = -1;
        int min = Integer.MAX_VALUE;
        for (int i = list.size()-1; i >= 0 && list.get(i).first == max; i--) {
            if (list.get(i).second.second - list.get(i).second.first < min){
                min = list.get(i).second.second - list.get(i).second.first;
                index = i;
            }
        }
        out.print((list.get(index).second.first+1) +" " + (list.get(index).second.second+1));
    }
    class Item{
        int start;
        int end;
        int frequency;
        public Item (int start, int end, int fre) {
            this.start = start;
            this.end = end;
            this.frequency = fre;
        }
    }