Kết hợp các mảng với các giá trị chồng chéo

Question

Im sử dụng Node.js. (... và underscore.js)

Xem xét cấu trúc dữ liệu này

var numbers = [ 
    [10, 20] 
    [30, 40] 
    [40, 50] 
    [45, 70] 
    ... //Possibly more arrays (always contains two numbers) 
] 

numbers chứa mảng đó luôn chứa các cặp số. Hãy nghĩ về các cặp số này là "bắt đầu" và "kết thúc". Tôi muốn một hàm lấy numbers làm đối số và vòng lặp máng nội dung của nó và nếu số "bắt đầu" của một cặp chồng lên số "cuối" của cặp trước đó, các mảng này được hợp nhất thành một. Ví dụ này:

var numbers = [ 
    [10, 20] 
    [19, 40] 
    [40, 60] 
    [70, 80] 
] 

trở thành này:

var numbers = [ 
    [10, 60] // First, second and third array is merged because of overlapping . 
    [70, 80] 
] 

Thực ra, tôi đã có viết một chức năng cho điều này mà hoạt động tốt, nhưng cảm thấy một chút thời gian.

Tôi rất tò mò nếu một số thuật sĩ javascript có thể làm mê hoặc tôi bằng giải pháp siêu thanh lịch =).

Answer 1

Tạo một trống rỗng "kết quả " mảng. Lặp qua mảng phạm vi và thay đổi mục cuối cùng của kết quả hoặc thêm phạm vi hiện tại vào đó.

function merge(ranges) { 
 
    var result = [], last; 
 

 
    ranges.forEach(function (r) { 
 
     if (!last || r[0] > last[1]) 
 
      result.push(last = r); 
 
     else if (r[1] > last[1]) 
 
      last[1] = r[1]; 
 
    }); 
 

 
    return result; 
 
} 
 

 
r = [[10, 20], [19, 40], [40, 60], [70, 80]]; 
 
document.write(JSON.stringify(merge(r)));

này giả định rằng các mảng nguồn được sắp xếp, nếu nó không phải luôn luôn như vậy, sắp xếp nó trước khi sáp nhập:

ranges.sort(function(a, b) { return a[0]-b[0] || a[1]-b[1] }); 

Answer 2

Tôi tạo ra một chức năng mà làm những gì bạn muốn:

function merge(arr) { 
    // copy and sort the array 
    var result = arr.slice().sort(function(a, b) { 
      return a[0] > b[0]; 
     }), 
     i = 0; 

    while(i < result.length - 1) { 
     var current = result[i], 
      next = result[i+1]; 

     // check if there is an overlapping 
     if(current[1] >= next[0]) { 
      current[1] = Math.max(current[1], next[1]); 
      // remove next 
      result.splice(i+1, 1); 
     } else { 
      // move to next 
      i++; 
     } 
    } 
    return result; 
}; 

Chức năng này có thể được sử dụng theo cách này:

var mergedNumbers = merge(numbers); 

DEMO

Answer 3

Như @Brett nói, đây có thể là một phù hợp hơn cho Code Review (chỉ cần chắc chắn bao gồm việc triển khai hiện tại của bạn). Nếu bạn đăng ở đó, đặt một tham chiếu đến nó ở đâu đó và tôi sẽ di chuyển câu trả lời của tôi.

---

Giả sử rằng mảng numbers của bạn đã được sắp xếp một cách chính xác, chức năng này nên làm những gì bạn muốn:

function combine(numbers) { 
 
    return numbers.reduce(function(combined, next) { 
 
     if (!combined.length || combined[combined.length-1][1] < next[0]) combined.push(next); 
 
     else { 
 
      var prev = combined.pop(); 
 
      combined.push([prev[0], Math.max(prev[1], next[1])]); 
 
     } 
 
    \t return combined; 
 
    }, []); 
 
} \t \t 
 

 
var n = [[10, 20], [19, 40], [40, 60], [70, 80], [75, 76]]; 
 
var r = combine(n); 
 
document.write('<pre>' + JSON.stringify(r) + '</pre>');

này "reduce s" mảng ban đầu cho cái mới sử dụng logic sau trong hàm reduce:

1. Nếu đây là lần đầu tiên vượt qua hoặc mục cuối cùng không chồng chéo mục hiện tại, push mục hiện tại vào mảng combined.
2. Nếu không:
   1. pop mục cuối cùng khỏi mảng combined.
   2. push sự kết hợp của mục cuối cùng và mục hiện hành về đến các mảng combined.