java - 在这种情况下使用哪种数据结构

Question

我有一个“代码标记”形式的输入字符串列表

例如，

1001-40
1002-54
1003-23
1001-45
1004-60

预期输出：

1004-60
1002-54
1001-45
1003-23

如果值重复（如 1001），则使用最新的值，也需要排序。

我的第一个赌注是使用 TreeMap，但它会带来基于值的排序问题，这是不可能的。

Scanner in = new Scanner(System.in);
        SortedMap<Integer, Integer> map = new TreeMap<Integer, Integer>(new Comparator<Integer>() {
            public int compare(Integer i, Integer j) {
                return(j.compareTo(i));
            }
        });

        int i=0;
        while(i<5)
        {
            String[] s = in.next().split("\\-");
            map.put(Integer.parseInt(s[0]),Integer.parseInt(s[1]));
            i++;
        }
        // Get a set of the entries
        Set set = map.entrySet();
        // Get an iterator
        Iterator itr = set.iterator();
        // Display elements
        while(itr.hasNext()) {
            Map.Entry me = (Map.Entry)itr.next();
            System.out.print(me.getKey() + ": ");
            System.out.println(me.getValue());
        }

解决这种情况的最佳方法是什么？

Answer 1

我从@Pshemo 发布的链接中窃取了代码，然后将您的数据设置为main模拟单元测试的一部分。先编码再输出。

代码

import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeMap;

/**
 * Group of code marks
 */
public class CodeMarks {
    /**
     * Keep track of the most recently added suffix (value) by prefix (key)
     */
    HashMap<Integer, Integer> codeMarks = new HashMap<Integer, Integer>();

    /**
     * Add a code mark (i.e. ####-##) to the group.
     * If same prefix already exists overwrite.
     *
     * @param codeMark
     */
    public void add(String codeMark) {
        // add some validation here
        String[] pieces = codeMark.split("\\-");
        Integer prefix = Integer.parseInt(pieces[0]);
        Integer suffix = Integer.parseInt(pieces[1]);
        codeMarks.put(prefix, suffix);
    }

    /**
     * Sort code marks in descending suffix order.
     */
    Comparator<Integer> comparator = new Comparator<Integer>() {
        @Override
        public int compare(Integer prefixA, Integer prefixB) {
            Integer suffixA = codeMarks.get(prefixA);
            Integer suffixB = codeMarks.get(prefixB);
            if (suffixB.equals(suffixA))
                return prefixB.compareTo(prefixA);
            else
                return suffixB.compareTo(suffixA);
        }
    };

    /**
     * Output all code marks in descending suffix order
     */
    public String toString() {
        TreeMap<Integer,Integer> sorted_map  = new TreeMap<Integer,Integer>(comparator);
        sorted_map.putAll(codeMarks);
        StringBuffer output = new StringBuffer();
        for (Integer prefix : sorted_map.keySet()) {
            Integer suffix = sorted_map.get(prefix);
            output.append(prefix + "-" + suffix + "\n");
        }
        return output.toString();
    }

    public static void main(String args[]) {
        CodeMarks cm = new CodeMarks(){{
            add("1001-40");
            add("1002-54");
            add("1003-23");
            add("1001-45");
            add("1004-60");
        }};
        String expected =
                "1004-60\n" +
                "1002-54\n" +
                "1001-45\n" +
                "1003-23\n";
        String actual = cm.toString();
        System.out.println(actual);
        System.out.println("actual.equals(expected): " + actual.equals(expected));
    }
}

输出

1004-60
1002-54
1001-45
1003-23

actual.equals(expected): true

Answer 2

您可以HashMap<Integer,Integer>简单地使用，然后根据它们的值对其进行排序：

public LinkedHashMap<Integer,Integer> sortHashMapByValues(HashMap<Integer,Integer> passedMap) {
   List<Integer> mapKeys = new ArrayList<Integer>(passedMap.keySet());
   List<Integer> mapValues = new ArrayList<Integer>(passedMap.values());
   Collections.sort(mapValues);
   Collections.sort(mapKeys);

   LinkedHashMap<Integer,Integer> sortedMap = 
       new LinkedHashMap<Integer,Integer>();

   Iterator valueIt = mapValues.iterator();
   while (valueIt.hasNext()) {
       Object val = valueIt.next();
    Iterator keyIt = mapKeys.iterator();

    while (keyIt.hasNext()) {
        int key = (Integer)keyIt.next();
        int comp1 = (Integer)passedMap.get(key);
        int comp2 = (Integer)val;

        if (comp1 == comp2){
            passedMap.remove(key);
            mapKeys.remove(key);
            sortedMap.put(key,(Integer) val);
            break;
        }

    }

}
return sortedMap;
}

Answer 3

我会简单地使用 aHashMap<Code, CodeMark>来消除重复代码，然后将所有值放入 aList<CodeMark>中，然后按降序对这个列表进行排序。