Day29 Leetcode Array系列----Merge Intervals

tags: 2020IT30

本次題目 Merge Intervals by js

input1 = [[1,3],[2,6],[8,10],[15,18]]
output1 = [[1,6],[8,10],[15,18]]
//Explanation: Since intervals [1,3] and [2,6] overlaps, 
//merge them into [1,6].

input2 = [[1,4],[4,5]]
output2 = [[1,5]]
//Explanation: Intervals [1,4] and [4,5] are 
//considered overlapping.

思考路線

1. 做個 result 裝判斷過後的結果，可能是合併的也可能是原本的
2. 最個迴圈來跑一輪依序檢查
3. 兩個陣列內的數字有重疊，題目給予的陣列有排序，子陣列也有排序，可以利用前一個子陣列的最後一個元素去扣後一個子陣列第一個元素，如果是正的或等於 0 就代表兩個陣列重疊，負的就代表兩者不重疊
4. 如果重疊就把前一個子陣列的第一個元素與後一個子陣列的最後一個元素取出，組成新的陣列塞到 result 裡面
5. 因為合併兩個陣列所以迴圈的 ｉ 要往前多跳一個，不然子陣列會重複塞到 result 中
6. 如果兩個子陣列不重疊，就將這兩個陣列塞到 result 中
7. result 中可能會有重複的元素，要去除掉

Coding Time

input1 = [[1,3],[2,6],[8,10],[15,18]]
output1 = [[1,6],[8,10],[15,18]]
//Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
input2 = [[1,4],[4,5]]
output2 = [[1,5]]
//Explanation: Intervals [1,4] and [4,5] are considered overlapping.

function merge(ary){
  result = []            //裝判斷後的結果
  for(let i = 1; i < ary.length; i++){
    if(ary[i-1][1]-ary[i][0] >= 0){  
    //藉由子陣列元素相扣判斷是否重疊
      result.push([ary[i-1][0],ary[i][1]]) // 重疊就合併
      i += 1 // 合併後要往前多跳一個
    }else{
      // 不重疊就兩個陣列一起塞到 result 中
      result.push(ary[i-1])
      result.push(ary[i])
    }

    result = result.filter((arr,index)=>{   
    // 移除 result 中重疊的元素
      if(result.indexOf(arr) == index){
        return arr
      }
    })
  }
  console.log(result)
  return result
}

function expect(a,b){
  console.log( JSON.stringify(a) == JSON.stringify(b) )
}

expect(merge(input1),output1)
expect(merge(input2),output2)

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty