從給定範圍中排除幾個範圍

Question

我有一個範圍值爲[1,35]的數組。然後，在第二陣列我有其它範圍，像[2,5], [8,9]等

現在我需要從第一減去那些範圍，並獲得值等 [1-1]（如2-5被取出），則下一個[6,7]然後[10,35]。

所以基本上我想從第二個數組中取出範圍並從第一個中移除它們。

我該怎麼做？

Answer 1

您可以在下面的ES6功能。

它允許您在第一個參數中指定多個範圍，並假定它沒有重疊範圍。函數的返回值是一個基於第一個參數的數組，但是第二個參數中指定的範圍已從中刪除。原來陣列的過程中不發生變異：

function subtractRanges(a, b) { 
 
    // Take deep copy of a and sort it 
 
    a = a.map(x => [...x]).sort((x, y) => x[0] - y[0]); 
 
    // Take shallow copy of b and sort it 
 
    b = [...b].sort((x, y) => x[0] - y[0]); 
 

 
    var c = [], i = 0, j = 0; 
 
    while (i < a.length && j < b.length) { 
 
     var x = a[i], y = b[j]; 
 
     if (y[0] > x[0]) { 
 
      c.push([x[0], Math.min(y[0]-1, x[1])]); 
 
      if (y[1] < x[1]) { 
 
       x[0] = y[1]+1; 
 
       j++; 
 
      } else { 
 
       i++; 
 
      } 
 
     } else { 
 
      if (y[1] >= x[1]) { 
 
       i++; 
 
      } else { 
 
       if (y[1] >= x[0]) { 
 
        x[0] = y[1]+1; 
 
       } 
 
       j++; 
 
      } 
 
     } 
 
    } 
 
    // Add remainder of a, and return 
 
    return [...c, ...a.slice(i)]; 
 
} 
 

 
// Sample input 
 
var a = [ [1,35] ]; 
 
var b = [ [2,5], [8,9] ]; 
 

 
// Get result 
 
var result = subtractRanges(a, b) 
 

 
// Output result 
 
console.log(JSON.stringify(result));

Answer 2

你可以使用一個直接的方法與檢查範圍的各部分的範圍。它檢查每個可能的非重疊部分的組合。

此提案適用於未排序的數據。

  ----------------     [ 9, 24] given interval, denotes as r 
    0000000001111111111222222222233333333334 
    123456789interval result   rules     return 
1   ----------------     [ 9, 24] none    i[0]===r[0]&&i[0]===r[0] none 
2    -------      [17, 23] [ 9, 16][24, 24] i[0]>r[0]&&i[1]<r[1]  [r[0],i[0]-1][i[1]+1,[r[1]]] 
3      ----------   [21, 30] [ 9, 20]   i[0]>r[0]&&i[0]<r[1]  [r[0],i[0]-1] 
4  --------        [ 5, 12] [13, 24]   i[1]>r[0]&&i[1]<r[1]  [i[1]+1,r[1]] 
5 ----          [ 1, 4] [ 9, 24]   i[1]<r[0]    r 
6         ----- [33, 37] [ 9, 24]   i[0]>r[1]    r 

function minus(r, a) { 
 
    var newR = []; 
 
    r.forEach(function (b) { 
 
     function push(t) { if (t[0] <= t[1]) { newR.push(t); } } 
 
     var temp = b.slice(); 
 
     if (a[0] === b[0] && a[1] === b[1]) { // 1 
 
      return; 
 
     } 
 
     if (a[0] > b[0] && a[1] < b[1]) { // 2 
 
      push([b[0], a[0] - 1]); 
 
      push([a[1] + 1, b[1]]); 
 
      return; 
 
     } 
 
     if (a[0] > b[0] && a[0] < b[1]) { // 3 
 
      temp[1] = a[0] - 1; 
 
     } 
 
     if (a[1] < b[1] && a[1] > b[0]) { // 4 
 
      temp[0] = a[1] + 1; 
 
     } 
 
     push(temp); 
 
    }); 
 
    return newR; 
 
} 
 

 
var ranges = [[1, 35]], 
 
    values = [[2, 5], [8, 9]], 
 
    result = values.reduce(minus, ranges); 
 

 
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }