dijkstra like solution in Java


  • 3
    L
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    	List<int[]> result = new ArrayList<int[]>();
    	PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
    		public int compare(int[] pair1, int[] pair2){
    			return (nums1[pair1[0]] + nums2[pair1[1]]) - (nums1[pair2[0]] + nums2[pair2[1]]);
    		}
    	});
    
    	int length1 = nums1.length;
    	int length2 = nums2.length;
    	boolean[][] visited = new boolean[length1][length2];
    
    	add(pq, visited, nums1, nums2, 0, 0);
    	while(pq.size() > 0 && result.size() < k){
    		int[] next = pq.poll();
    		result.add(new int[]{nums1[next[0]], nums2[next[1]]});
    		add(pq, visited, nums1, nums2, next[0] + 1, next[1]);
    		add(pq, visited, nums1, nums2, next[0], next[1] + 1);
    	}
    
    	return result;
    }
    
    private void add(PriorityQueue<int[]> pq, boolean[][] visited, int[] nums1, int[] nums2, int n1, int n2){
    	if(n1 < nums1.length && n2 < nums2.length && !visited[n1][n2]){
    		pq.add(new int[]{n1, n2});
    		visited[n1][n2] = true;
    	}
    }

Log in to reply
 

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