Java O(N * logN) , detailed explain


  • 0
    M

    The idea is simple, first sort the array by rules:
    Two people : a,b
    if a[0] > b[0] then a<b;
    if a[0] < b[0] then a>b;
    if a[0] = b[0] then sort by people[1];
    if a[1] > b[1] then a>b;
    ...

    for example, input:
    [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    after sort:
    [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

    next step, put the people in a list at specified position. Iterate the sorted array, when we pick a people , the people before is higher or equal to that. So we just put it according to the position people[1];

    Here is the code:

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            if(people.length == 0) return new int[][]{};
    
            //sort
            Arrays.sort(people,new mC());
    
            //put in a list
            List<int[]> list = new LinkedList<>();
            list.add(people[0]);
            for (int i =1;i<people.length;i++) {
                list.add(people[i][1],people[i]);
            }
            
            //return result
            Iterator iterator = list.iterator();
            int i = 0;
            while (iterator.hasNext()) {
                people[i++] = (int[]) iterator.next();
            }
            return people;
        }
        class  mC implements Comparator<int[]> {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] > o2[0]) return -1;
                else if (o1[0] < o2[0]) return 1;
                else {
                    return o1[1] - o2[1];
                }
            }
        };
    }

  • 0
    M

    I think the complexity of 'list.add' will be O(N^2) in the worst cast, that's to say you insert the element at the first place every time.


  • 0
    C

    @merryChris Agree. Not only for worst case, even for average, it is also O(n^2)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.