京东编程题（Java）AC 1.27

1. 合唱排队问题 (ac)

样例输入1：
4
2 1 3 2
样例输出1：
2
解释：
(1,2), (2, 3)

所以这题的思路肯定是要排序的，然后使用map来统计左右边界的问题，既然有左右边界，所以需要2个指针h1(高度1), h2(高度2)，再加一个变量count统计遍历来看h1和h2指向的元素相等的个数

原始数组nums: 2  1  3  2       map           count
            h1                2:1,1:-1        2   (h1=2, h2=1,有2个不相等)
排序数组temp: 1  2  2  3
            h2

原始数组nums: 2  1  3  2       map            count
               h1             2:0, 1:0        0       ans ++;
排序数组temp: 1  2  2  3
               h2

原始数组nums: 2  1  3  2       map            count
                  h1         3:1, 2:1         2  (h1=3, h2=2,有2个不等)     
排序数组temp: 1  2  2  3
                  h2

原始数组nums: 2  1  3  2       map            count
                      h1      3:0, 2:0        0     ans ++;     
排序数组temp: 1  2  2  3
                      h2

static void solve() throws IOException {
        int n = nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = nextInt();
        }
        Map<Integer, Integer> map = new HashMap<>();

        int ans = 0;
        int count = 0;
        int[] temp = new int[n];
        System.arraycopy(nums, 0, temp, 0, nums.length);
        Arrays.sort(temp);
        for (int i = 0; i < nums.length; ++i) {
            int h1 = nums[i];
            int h2 = temp[i];

            map.put(h1, map.getOrDefault(h1, 0) + 1);
            if (map.get(h1) == 0) count--;
            if (map.get(h1) == 1) count++;

            map.put(h2, map.getOrDefault(h2, 0) - 1);
            if (map.get(h2) == -1) count++;
            if (map.get(h2) == 0) count--;

            if (count == 0) ans++;
        }

        System.out.println(ans);
    }

2. 班级排列问题 (27%，但是给出应该ac的方法)

重点就在字典序上
样例输入1：
2 2
1 3
1 4
样例输出：
1
1 （字典序）

再看一组样例
样例输入1：
2 2
1 3
2 3
样例输出：
1
3 （而不是1 2）

再看一组样例
样例输入1：
20 5
2 22
1 25
11 24
3 21
1 22
样例输出：
4
1 11 2 3 （而不是1 2 3 11）

我就跪在了字典序上。没有理解字典序，只过了27%，还没有理解把女生赶出去可能比把男生赶出去更好的情况。

static void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        List[] list = new ArrayList[2 * n + 1];
        for (int i = 0; i < list.length; i++) {
            list[i] = new ArrayList();
            // 放入原始索引
            list[i].add(i);
        }
        // 相当于建立无向图
        for (int i = 0; i < m; i++) {
            int boy = nextInt();
            int girl = nextInt();
            list[boy].add(girl);
            list[girl].add(boy);
        }
        // 按size()逆序, 相当于找度最大的
        Arrays.sort(list, (o1, o2) -> o2.size() - o1.size());
        List<Integer> idx = new ArrayList<>();
        for (int i = 0; i < list.length; i++) {
            // 查找两个集合入过没有交集 (相当于删除一个节点, 如果有交集，表示与这个节点之前的联系还存在)
            if (list[i].size() > 1 && notContains(list[i], idx)) {
                // 获取原始索引
                idx.add((Integer)list[i].get(0));
            }
        }
        // 打印需要赶出去的个数
        System.out.println(idx.size());
        // 转为String，求字典序
        List<String> idx2 = new ArrayList<>();
        for (int i: idx
             ) {
            idx2.add(i+"");
        }
        // 按字典序
        idx2.sort(String::compareTo);
        for (int i = 0; i < idx2.size(); i++) {
            System.out.print(idx2.get(i) + " ");
        }
    }

    // 两个集合没有交集
    public static boolean notContains(List<Integer> list1, List<Integer> list2) {
        for (int i = 0; i < list1.size(); i++) {
            if (list2.contains(list1.get(i))) {
                return false;
            }
        }
        return true;
    }