Java solution using PriorityQueue and LinkedList


  • 6

    Instead of using ArrayList for insertion, using LinkedList is more efficient. Here is the discussion of when to use LinkedList over ArrayList on StackOverFlow.

    public class Solution {
        class PairComp implements Comparator<int[]> {
            public int compare(int[] p1, int[] p2){
                int comp_h = Integer.compare(p2[0], p1[0]);
                return comp_h == 0 ? Integer.compare(p1[1], p2[1]): comp_h;
            }
        }
        public int[][] reconstructQueue(int[][] people) {
            LinkedList<int[]> list = new LinkedList();
            PriorityQueue<int[]> queue = new PriorityQueue<int[]>(1, new PairComp() );
            for (int[] ppl: people){
                queue.offer( ppl );
            }
            while ( ! queue.isEmpty() ) {
                int[] pair = queue.poll();
                list.add(pair[1], pair);
            }
            int[][] ret = new int[people.length][];
            for (int i=0; i<list.size(); i++){
                ret[i] = list.get(i);
            }
            return ret;
        }
    }
    

    Shorter version without using PriorityQueue:

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people,new Comparator<int[]>(){
               public int compare(int[] p1, int[] p2){
                   return p1[0]!=p2[0]?Integer.compare(p2[0],p1[0]): Integer.compare(p1[1],p2[1]);
               }
            });
            List<int[]> list = new LinkedList();
            for (int[] ppl: people) list.add(ppl[1], ppl);
            return list.toArray(new int[people.length][] );
        }
    }
    

  • 0
    Z
    This post is deleted!

  • 0
    B

    what a brilliant idea!!


  • 5

    What exactly makes you think LinkedList is more efficient than ArrayList? I tried your (second) solution with both, each three times, alternating between the versions:

    LinkedList: 20 ms
    ArrayList: 17 ms
    LinkedList: 21 ms
    ArrayList: 19 ms
    LinkedList: 22 ms
    ArrayList: 15 ms

    ArrayList looks like the clear winner to me.

    Then I did this to make that second part take more time and thus reduce the impact of the sorting:

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people,new Comparator<int[]>(){
               public int compare(int[] p1, int[] p2){
                   return p1[0]!=p2[0]?Integer.compare(p2[0],p1[0]): Integer.compare(p1[1],p2[1]);
               }
            });
            List<int[]> list = new LinkedList();
            for (int i=0; i<100; i++) {
                list = new LinkedList();
                for (int[] ppl: people) list.add(ppl[1], ppl);
            }
            return list.toArray(new int[people.length][] );
        }
    }
    

    LinkedList: 431 ms, 239 ms, 411 ms
    ArrayList: 143 ms, 147 ms, 131 ms

    Here ArrayList was the even much clearer winner.


  • 0
    H

    @StefanPochmann said in Java solution using PriorityQueue and LinkedList:

    I agree, linklist is not necessary more efficient than arraylist here.
    I think they theoretically equivalent in add(position, item);

    for linklist, it take o(n) to get to position;
    for arraylist, it take o(n) to move elements after position to the back.(seems like there is a super fast system call to do this)

    :) I might be wrong, pls let me know if i am.


  • 0

    @henry91w I'd say you're right except that they're not o(n) but O(n).


Log in to reply
 

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