尋找右區間

給定一組區間，對于每一個區間 i，檢查是否存在一個區間 j，它的起始點大于或等于區間?i 的終點，這可以稱為 j 在 i 的"右側"。

對于任何區間，你需要存儲的滿足條件的區間?j 的最小索引，這意味著區間 j 有最小的起始點可以使其成為"右側"區間。如果區間?j 不存在，則將區間 i 存儲為 -1。最后，你需要輸出一個值為存儲的區間值的數組。

注意:

你可以假設區間的終點總是大于它的起始點。

你可以假定這些區間都不具有相同的起始點。

示例 1:

輸入: [ [1,2] ]

輸出: [-1]

?

解釋:集合中只有一個區間，所以輸出-1。

示例 2:

輸入: [ [3,4], [2,3], [1,2] ]

輸出: [-1, 0, 1]

?

解釋:對于[3,4]，沒有滿足條件的"右側"區間。

對于[2,3]，區間[3,4]具有最小的"右"起點;

對于[1,2]，區間[2,3]具有最小的"右"起點。

示例 3:

輸入: [ [1,4], [2,3], [3,4] ]

輸出: [-1, 2, -1]

?

解釋:對于區間[1,4]和[3,4]，沒有滿足條件的"右側"區間。

對于[2,3]，區間[3,4]有最小的"右"起點。

?

?

?

?

?

?

解題思路

利用java TreeMap的性質，把所有區間的左邊界作為key值，所在位置作為value值，保存在map中，利用TreeMap中已有的ceilingKey(key k)方法，直接獲取與給定key大且最近的key值，然后通過key值得到位置。

1 /** 2 * Definition for an interval. 3 * public class Interval { 4 * int start; 5 * int end; 6 * Interval() { start = 0; end = 0; } 7 * Interval(int s, int e) { start = s; end = e; } 8 * } 9 */ 10 import java.util.TreeMap; 11 12 public class Solution{ 13 public int[] findRightInterval(Interval[] intervals){ 14 int len=intervals.length; 15 int nums[]=new int[len]; 16 TreeMap<Integer,Integer> map=new TreeMap<Integer,Integer>(); 17 for(int i=0;i<len;i++){ 18 map.put(intervals[i].start,i); 19 } 20 for(int i=0;i<len;i++){ 21 Integer num=map.ceilingKey(intervals[i].end); 22 if(num==null){ 23 nums[i]=-1; 24 }else{ 25 nums[i]=map.get(num); 26 } 27 } 28 return nums; 29 } 30 }

?

轉載于:https://www.cnblogs.com/kexinxin/p/10269825.html

總結

以上是生活随笔為你收集整理的Leetcode 436.寻找右区间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。