iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 18
1
Software Development

LeetCode30系列 第 18

[LeetCode30] Day4 - 876. Middle of the Linked List

題目

  • 你有一個區間數組intervals, 其中每個區間intervals[i]=[start, end],而每個區間的start都是唯一的,不會重複數字。
  • 要返回一個array,為每個區間*intervals[i]*的右區間的index,如果沒有則是-1。
  • 右區間的定義
    • 區間intervals[i]intervals[j],其中start_j >= end_istart_j為最小值
  • Example:
    • [[3,4],[2,3],[1,2]]
    • 返回 [-1, 0, 1]
      • [3,4]沒有右區間,所以為-1。
      • [2,3]的右區間為[3,4],而[3,4]的index為0。
      • [1,2]的右區間為[2,3],而[2,3]的index為1。

解法

  • 基本思路:我們先以每個區間start去做排序,再以每個區間的end,去找符合右區間的規定。
  • 如果直接將區間數組做排序,我們沒辦法得到原本每個區間的index,所以要先處理這個問題,因為要以每個區間的start去做排序,所以我們就先以start做為key,value做為index,儲存到hash table,用hash table是因為通常能有很好的搜索性能,這前面的題目有提過(應該)。
  • 另外也建一個array,稱做starts,儲存每個區間start。
  • 接著對starts排序
  • 使用C++ STL提供的upper_bound,功能就如字面的意思,就是給定一個有序的範圍*[L,R],並給予一個值val*,會返回在這範圍[L,R]中,第一個大於val的值的index。
  • 那我們依序將val=每個區間的end,,並在排序好的starts找upper_bound,就會是 大於end的最小start(沒找到就直接給-1),並拿去hash table中索引,就能找到原本的index,即我們要的答案。

Code

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<int> ans;
        vector<int> starts; 
        unordered_map<int,int> map; //hash table
        
        for(int i = 0; i< intervals.size(); i++){
            map[intervals[i][0]] = i; // key: start_i, value: i (index),
            starts.push_back(intervals[i][0]);  
        }
        
        sort(starts.begin(), starts.end());
        
        for(int i = 0; i< intervals.size(); i++){
            auto search_res = upper_bound(starts.begin(), starts.end(), intervals[i][1] - 1);
            if(search_res == starts.end()){
                ans.push_back(-1);
            } 
			else{ 
                ans.push_back(map[*search_res]);
            }
        }
		return ans;
    }
};

https://ithelp.ithome.com.tw/upload/images/20201003/20129147X31GdUO7UC.png
後來想到C++ STL中 map底層是用red-black tree實現的,所以使用它來儲存key-value pair會保持有序,與底層用hash table實現的unordered_map不同,所以本身也就有提供upper_bound與lower_bound。所以也附上來。
另外你問我結果怎看起來差不多,是因為我跑很多次取好看的哈哈,map理論上比較穩定O(lgn),unordered_map則時快時慢,因為hash table有可能從O(1)變O(n),但好像有點吃leetcode測資,map有時也會很慢,我猜是做了很大量的平衡。 反正那個數字就參考參考。

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<int> ans;
        map<int,int> map;
        
        for(int i = 0; i< intervals.size(); i++){
            map[intervals[i][0]] = i;
        }
        
        for(int i = 0; i< intervals.size(); i++){
            auto search_res = map.lower_bound(intervals[i][1]);
            if(search_res == map.end()){
                ans.push_back(-1);
            } 
			else{ 
                ans.push_back(search_res->second);
            }
        }
		return ans;
    }
};

https://ithelp.ithome.com.tw/upload/images/20201003/20129147rH1xECkuWQ.png


上一篇
[LeetCode30] Day17 - 48. Rotate Image
下一篇
[LeetCode30] Day19 - 6. ZigZag Conversion
系列文
LeetCode3030

尚未有邦友留言

立即登入留言