1, Leetccode1743 multiple processing methods

On the third day, I found that the first question in the leetcode question bank was given randomly every day. Two simple questions were given to me two days ago. Today, I came directly to a medium question.
Adhering to the ability to cultivate algorithmic thinking and independent thinking, I have worn it for a long time today. See the figure below to see how persistent I am. In fact, the first time was right, but its test data was really too large. I clicked on the details and found that the input data was as large as the sample data used to train the neural network.
Independent thinking route:
->Write your own linked list. You want to use the one-way linked list with the leading pointer and the tail pointer.
->Use ArrayList for the output data
->ArrayList is used for input data and output data
->HashMap

2, Detailed explanation of various treatment methods

1. Unidirectional linked list with head and tail pointers

The first attempt, this idea is not wrong, but this is a moderately difficult problem, which requires high time complexity.

1. Theoretical knowledge

1. Establish a one-way linked list with head and tail pointers
2. Find the left and right elements by looping
3. The left and right elements are inserted by head interpolation and tail interpolation
4. Time complexity:

a. Number of runs k=(n-1)*n/2
b. Time complexity is O(n^2)

2. Source code

class Node {
    private int data;
    private Node next;

    public Node() {
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}
public static int[] restoreArray(int[][] adjacentPairs) {

        Node l = new Node();
        l.setNext(null);
        Node r = new Node();
        r.setNext(null);
        Node lp = new Node();
        Node rp = new Node();
        lp = l;
        rp = r;
        l.setData(adjacentPairs[0][0]);
        r.setData(adjacentPairs[0][1]);
        l.setNext(r);
        adjacentPairs[0][0] = adjacentPairs[0][1] = 0;
        for (int i = 1; i < adjacentPairs.length; i++) {
            Node data = new Node();
            for (int j = 0; j < adjacentPairs.length; j++) {
                if (adjacentPairs[j][0] == adjacentPairs[j][1])
                    continue;
                if (adjacentPairs[j][0] != lp.getData() && adjacentPairs[j][0] != rp.getData() && adjacentPairs[j][1] != lp.getData() && adjacentPairs[j][1] != rp.getData())
                    continue;
                if (adjacentPairs[j][0] == lp.getData()) {
                    data.setData(adjacentPairs[j][1]);
                    data.setNext(lp);
                    lp = data;
                } else if (adjacentPairs[j][0] == rp.getData()) {
                    rp.setNext(data);
                    data.setNext(null);
                    data.setData(adjacentPairs[j][1]);
                    rp = data;
                } else if (adjacentPairs[j][1] == lp.getData()) {
                    data.setNext(lp);
                    data.setData(adjacentPairs[j][0]);
                    lp = data;
                } else {
                    rp.setNext(data);
                    data.setNext(null);
                    data.setData(adjacentPairs[j][0]);
                    rp = data;
                }
                adjacentPairs[j][0] = adjacentPairs[j][1] = 0;
                break;
            }
        }
        int[] nums = new int[adjacentPairs.length + 1];
        int i = 0;
        while (lp != null) {
            nums[i] = lp.getData();
            lp = lp.getNext();
            i++;
        }
        return nums;
    }

2,ArrayList

The second attempt is similar to the third attempt, but the number of times of using ArrayList is different. I recorded it here.

1. Theoretical knowledge

1. Similar to the above logic, it only uses ArrayList to store and ArrayList features to implement header and tail insertion.
2. Time complexity: O(n^2)

2. Source code

public static int[] restoreArray(int[][] adjacentPairs) {
        ArrayList<Integer> a = new ArrayList<>();
        a.add(adjacentPairs[0][0]);
        a.add(adjacentPairs[0][1]);
        List<List<Integer>> b = new ArrayList<>();
        for (int i = 0; i < adjacentPairs.length - 1; i++) {
            ArrayList<Integer> c = new ArrayList<>();
            c.add(0, adjacentPairs[i + 1][0]);
            c.add(1, adjacentPairs[i + 1][1]);
            b.add(i, c);
        }
        //adjacentPairs[0][0] = adjacentPairs[0][1] = 0;
        int n = adjacentPairs.length;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < b.size(); j++) {
                if (!b.get(j).get(0).equals(a.get(0)) && !b.get(j).get(0).equals(a.get(a.size() - 1)) && !b.get(j).get(1).equals(a.get(0)) && !b.get(j).get(1).equals(a.get(a.size() - 1))) {
                    continue;
                }
                if (b.get(j).get(0).equals(a.get(0))) {
                    a.add(0, b.get(j).get(1));
                } else if (b.get(j).get(0).equals(a.get(a.size() - 1))) {
                    a.add(b.get(j).get(1));
                } else if (b.get(j).get(1).equals(a.get(0))) {
                    a.add(0, b.get(j).get(0));
                } else {
                    a.add(b.get(j).get(0));
                }
                b.remove(j);
                //adjacentPairs[j][0] = adjacentPairs[j][1]=0;
                break;
            }
        }
        int[] nums = new int[n + 1];
        for (int i = 0; i < a.size(); i++) {
            nums[i] = a.get(i);
        }
        return nums;
    }

3,HashMap

To tell the truth, I've forgotten this Map a little. I've tried my best to think independently. Adhering to the learning habit of learning without thinking, it's useless, and thinking without learning is dangerous. I went to see the comment solution and saw the words of Hash Map, which woke me up. I probably looked at the source code, so I thought about the way of HashMap to improve the running speed.

1. Theoretical knowledge

1. Create a HashMap, save yourself as a key, and save adjacent elements as value (ArrayList).
2. The first element is found through the first element or the last element with only one precursor and successor element.
3. Quickly find the subsequent elements of the obtained elements through HashMap, and then cycle like this.
4. Time complexity: O(n). The complexity of HashMap is not considered. After all, the search element under hash conflict must be less than O(n).

2. Source code

public static int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, ArrayList<Integer>> m = new HashMap<>();
        for (int i = 0; i < adjacentPairs.length; i++) {
            m.computeIfAbsent(adjacentPairs[i][0], row -> new ArrayList<>()).add(adjacentPairs[i][1]);
            m.computeIfAbsent(adjacentPairs[i][1], row -> new ArrayList<>()).add(adjacentPairs[i][0]);
        }
        int[] nums = new int[adjacentPairs.length + 1];
        for (Map.Entry<Integer, ArrayList<Integer>> entry : m.entrySet()) {
            if (entry.getValue().size() == 1) {
                nums[0] = entry.getKey();
                nums[1] = entry.getValue().get(0);
                break;
            }
        }
        for (int i = 0; i < adjacentPairs.length - 1; i++) {
            ArrayList<Integer> data = m.get(nums[i + 1]);
            nums[i + 2] = data.get(0) != nums[i] ? data.get(0) : data.get(1);
        }
        return nums;
    }

3, Extension – why does HashMap find elements so quickly?