忽略重叠数计算数字数组的总数

Question

我遇到了这种问题，正在尝试使用 Javascript/Go 来解决它。给定这个数字集数组，我想找到数字的总和。计算应该忽略重叠，考虑只算一次。

const nums = [[10, 26], [43, 60], [24,31], [40,50], [13, 19]]

如果翻译成图片的话就是下面这样了

结果应该41

规则是

重叠的一组数（粉色区域）应该算一次
统计绿化面积总和。
两者合计。

我们将不胜感激。

Answer 1

这是一个使用 javascript 的单行解决方案（假设正确答案是 41 而不是 42）。

想法是迭代所有区间数并将它们放在一个数组中，然后 trim 使用 Set 所有重复项。时间复杂度不是最优但足够短。

const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]];

const total = new Set(nums.reduce((acc, [from, to]) => 
  [...acc, ...Array.from({ length: to - from }, (_, i) => i + from)], [])).size;

console.log(total);

不确定如何使用 go 但这只是一个建议。

Answer 2

这是我的版本：

const getCoverage = arr => arr
  .reduce((results, el) => {
    if (!results.length) { 
      return [el];
    }
    let running = true, i = 0;
    while(running && i < results.length) {
      if (el.some(n => n >= results[i][0] && n <= results[i][1])) {
        results[i] = [
          Math.min(el[0], results[i][0]),
          Math.max(el[1], results[i][1])
        ];
        running = false;
      } 
      i++;
    }
    if (running) {
      results.push(el);
    }
    return results;
  }, [])
  .reduce((total, el) => el[1] - el[0] + total, 0);

console.log(
  getCoverage([[10, 26], [43, 60], [24,31], [40,50], [13, 19]])
);

第一个 reducer 合并重叠（和相邻）区间，第二个 reducer 将合并结果的差异相加。

Answer 3

您可以通过检查第二个值对对和归约进行排序，然后添加增量以获得总和。

const
    nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]],
    result = nums
        .sort((a, b) => a[0] - b[0] || a[1] - b[1])
        .reduce((r, [...a]) => {
            const last = r[r.length - 1];
            if (last && last[1] >= a[0]) last[1] = Math.max(last[1], a[1]);
            else r.push(a);
            return r;
        }, [])
        .reduce((s, [l, r]) => s + r - l, 0);

console.log(result)

Answer 4

您可以将给定二维数组的值散布在一个数组中并对它们进行排序。计算非重叠数组的边缘值之间的差异之和与重叠区域内值的差异之和，结果将是两者之间的差异。

const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]]
let arr = []
//spread given 2-D array
nums.forEach(item => arr=[...arr,...item]);
// Sort both arrays
arr.sort();
nums.sort();
let previtem, sum = 0;
let min , max ;
let count = 0;
//Loop to find sum of difference between non-overlapping values
nums.forEach((item,index) => {
        if (index === 0) {
           min = nums[0][0], max = nums[0][1]     
        }
        else if (!(item[0]>min && item[0]<max) && !(item[1]>min && item[1]<max))
        {
                flag = 1;
                count = count + (item[0] - max);
                min = item[0];
                max = item[1];
                console.log(item,count);
        }
        else if (item[0]>min && item[0]<max &&  !(item[1]>min && item[1]<max)) {
                max = item[1];
        }
})

// loop to find sum of difference of unique values within overlapping area
arr.forEach(item => {
        if (previtem && item !== previtem) {
                sum=sum+(item-previtem)
        }
        previtem = item;
})

//Print the result
console.log(sum - count);

忽略重叠数计算数字数组的总数

Count total of number array with ignoring overlap number

javascript

arrays

algorithm

math

go