algorithm/leetcode/RestoreTheArrayFromAdjacentPairs.java at master · skyczhao/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package leetcode;

import java.util.*;

/**
 * RestoreTheArrayFromAdjacentPairs
 * https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/
 * 1743. 从相邻元素对还原数组
 * https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/solution/que-ding-bian-jie-jie-fa-zi-ran-chu-by-o-9cr6/
 *
 * @author tobin
 * @since 2021-07-25
 */
public class RestoreTheArrayFromAdjacentPairs {
    public static void main(String[] args) {
        RestoreTheArrayFromAdjacentPairs sol = new RestoreTheArrayFromAdjacentPairs();

//        int[][] input = {{2, 1}, {3, 4}, {3, 2}};
//        int[][] input = {{4, -2}, {1, 4}, {-3, 1}};
        int[][] input = {{100000, -100000}};
        int[] res = sol.restoreArray(input);
        for (int value : res) {
            System.out.println(value);
        }
    }

    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, Integer> map_one = new HashMap<>();
        Map<Integer, Integer> map_two = new HashMap<>();
        Map<Integer, Integer> counts = new HashMap<>();
        for (int[] pair : adjacentPairs) {
            if (map_one.containsKey(pair[0])) {
                map_two.put(pair[0], pair[1]);
                counts.put(pair[0], 2);
            } else {
                map_one.put(pair[0], pair[1]);
                counts.put(pair[0], 1);
            }

            if (map_one.containsKey(pair[1])) {
                map_two.put(pair[1], pair[0]);
                counts.put(pair[1], 2);
            } else {
                map_one.put(pair[1], pair[0]);
                counts.put(pair[1], 1);
            }
        }

        // find edge
        List<Integer> edges = new LinkedList<>();
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                edges.add(entry.getKey());
            }
        }
        if (edges.size() != 2) {
            return null;
        }

        // build result
        int size = map_one.size();
        int[] result = new int[size];
        int next = edges.get(0);
        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < size; i++) {
            result[i] = next;
            used.add(next);

            int tmp = map_one.get(next);
            if (next == edges.get(1)) {
                break;
            } else if (used.contains(tmp)) {
                tmp = map_two.get(next);
            }
            next = tmp;
        }

        return result;
    }
}