题解 | #有重复项数字的所有排列#
有重复项数字的所有排列
http://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863
package org.example.test; import com.alibaba.fastjson.JSONObject; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.Map; public class BackTrackTest { public static void main(String[] args) { int[] test = {1, 1, 2}; System.out.println(JSONObject.toJSONString(permuteUnique(test))); } static ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); /** * 回溯+去重+排序 * * @param num * @return */ public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { int len = num.length; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < num.length; i++) { map.put(i, num[i]); } ArrayList<Integer> track = new ArrayList<>(); back(map, track); HashMap<String, ArrayList<Integer>> map1 = new HashMap<>(); for (ArrayList<Integer> an : ans) { StringBuilder key = new StringBuilder(); for (int j = 0; j < num.length; j++) { key.append(an.get(j)); } map1.put(key.toString(), an); } ArrayList<ArrayList<Integer>> ans1 = new ArrayList<>(); for (Map.Entry<String, ArrayList<Integer>> entry : map1.entrySet()) { ans1.add(entry.getValue()); } ans1.sort(new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) { StringBuilder key1 = new StringBuilder(); StringBuilder key2 = new StringBuilder(); for (int i = 0; i < len; i++) { key1.append(o1.get(i)); key2.append(o2.get(i)); } return key1.toString().compareTo(key2.toString()); } }); return ans1; } private static void back(Map<Integer, Integer> num, ArrayList<Integer> track) { if (track.size() == num.size()) { ArrayList<Integer> tmp = new ArrayList<>(); for (Integer value : track) { tmp.add(num.get(value)); } ans.add(tmp); return; } for (Map.Entry<Integer, Integer> entry : num.entrySet()) { Integer key = entry.getKey(); if (track.contains(key)) { continue; } track.add(key); back(num, track); track.remove(track.size() - 1); } } }
算法 文章被收录于专栏
数据结构和算法