题解 | #有重复项数字的所有排列#

有重复项数字的所有排列

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);
        }
    }
}
算法 文章被收录于专栏

数据结构和算法

全部评论

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司7个岗位
点赞 评论 收藏
分享
05-25 10:45
门头沟学院 Java
Frank_zhan...:没实习一个项目肯定不够,可以再做一个轮子,技术栈再补一个mq,微服务,整体再换个简历模板,暑期尽量再找一个日常实习
无实习如何秋招上岸
点赞 评论 收藏
分享
零OFFER战士:另一个版本查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务