我有一个无序数组:[2,2,3,1,1,5,4],求输出[1,1],[2,2](数组的元素)或者[3,4],[0,1](数组的索引)最快的算法。要求时间复杂度小于O(n2)。(备注:这个两个数组不要求有序,即[2,2],[1,1]也是可以的)。
Map<String, List<Book>> repeatMap = new HashMap<>(); Map<String, Book> existMap = new HashMap<>(); for (Book book : bookList) { String key = book.getName(); boolean containsKey = existMap.containsKey(key); // 如果已经存在了,那么就说明已经重复了 if (containsKey) { boolean containsInMap = repeatMap.containsKey(key); // 没有添加过 if (!containsInMap) { List<Book> repeatList = new ArrayList<>(); // 转移 Book existBook = existMap.remove(key); repeatList.add(existBook); repeatList.add(book); repeatMap.put(key, repeatList); } // 如果map中没有这个值,那么就直接保存 List<Book> repeatList = repeatMap.get(key); repeatList.add(book); } existMap.put(key, book); } // 对map进行求和,并加入到合并的list中 for (Map.Entry<String, List<Book>> entry : repeatMap.entrySet()) { List<Book> repeatList = entry.getValue(); Book first = repeatList.get(0); int i = 1; for (; i < repeatList.size() - 1; i++) { Book book = repeatList.get(i); Long oldVal = first.getCount(); Long incrementVal = book.getCount(); first.setCount(oldVal + incrementVal); } String key = first.getName(); existMap.put(key, first); } ArrayList<Book> bookArrayList = new ArrayList<>(existMap.values()); System.out.println(bookArrayList);
2.1m questions
2.1m answers
60 comments
56.8k users