计算数字数组的总数，忽略重复的数字。

huangapple
go评论125阅读模式
英文:

Count total of number array with ignoring overlap number

问题

我有这样一个问题，想用JavaScript/Go来解决。给定这个数字集合的数组，我想找到数字的总和。计算应该忽略重叠部分，并将其视为仅计算一次。

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

如果将其转化为图像，应该是这样的。

计算数字数组的总数，忽略重复的数字。

结果应该是41。

规则如下：

  • 重叠的数字集合（粉色区域）应该只计算一次。
  • 计算绿色区域的总和。
  • 两者相加。

任何帮助将不胜感激。

英文:

I have this kind of problem and trying to solve it by using Javascript/Go. Given this array of number set, I would like to find the sum of number. The calculation should ignore the overlap and consider to count it as only once.

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

It would be something like following if translated into the picture.

计算数字数组的总数，忽略重复的数字。

The result should 41

The rules are

  • Overlap set of number (pink area) should be count once.
  • Count total sum of green area.
  • Total for both.

Any help will be appreciated.

答案1

得分: 1

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

思路是遍历所有的区间数字，并将它们放入一个单独的数组中，然后使用Set去除所有的重复项。时间复杂度不是最优的，但足够简洁。

  1. const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]];
  3. const total = new Set(nums.reduce((acc, [from, to]) => 
  4.   [...acc, ...Array.from({ length: to - from }, (_, i) => i + from)], [])).size;
  6. console.log(total);

不确定如何在go中实现，但这只是一个提议。

英文:

Here's an one-liner solution using javascript (Assuming the correct answer is 41 instead of 42).

The idea is to iterate all interval numbers and put them in a single array, then trim all the duplicates using Set. The time complexity is not optimal but it's short enough.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]];
  3. const total = new Set(nums.reduce((acc, [from, to]) =&gt; 
  4.   [...acc, ...Array.from({ length: to - from }, (_, i) =&gt; i + from)], [])).size;
  6. console.log(total);

<!-- end snippet -->

Not sure how to do it with go but it's just a proposal.

答案2

得分: 1

这是我的版本：

  1. const getCoverage = arr => arr
  2.   .reduce((results, el) => {
  3.     if (!results.length) { 
  4.       return [el];
  5.     }
  6.     let running = true, i = 0;
  7.     while(running && i < results.length) {
  8.       if (el.some(n => n >= results[i][0] && n <= results[i][1])) {
  9.         results[i] = [
  10.           Math.min(el[0], results[i][0]),
  11.           Math.max(el[1], results[i][1])
  12.         ];
  13.         running = false;
  14.       } 
  15.       i++;
  16.     }
  17.     if (running) {
  18.       results.push(el);
  19.     }
  20.     return results;
  21.   }, [])
  22.   .reduce((total, el) => el[1] - el[0] + total, 0);
  24. console.log(
  25.   getCoverage([[10, 26], [43, 60], [24,31], [40,50], [13, 19]])
  26. );

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

英文:

Here's my version:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. const getCoverage = arr =&gt; arr
  2.   .reduce((results, el) =&gt; {
  3.     if (!results.length) { 
  4.       return [el];
  5.     }
  6.     let running = true, i = 0;
  7.     while(running &amp;&amp; i &lt; results.length) {
  8.       if (el.some(n =&gt; n &gt;= results[i][0] &amp;&amp; n &lt;= results[i][1])) {
  9.         results[i] = [
  10.           Math.min(el[0], results[i][0]),
  11.           Math.max(el[1], results[i][1])
  12.         ];
  13.         running = false;
  14.       } 
  15.       i++;
  16.     }
  17.     if (running) {
  18.       results.push(el);
  19.     }
  20.     return results;
  21.   }, [])
  22.   .reduce((total, el) =&gt; el[1] - el[0] + total, 0);
  24. console.log(
  25.   getCoverage([[10, 26], [43, 60], [24,31], [40,50], [13, 19]])
  26. );

<!-- end snippet -->

The first reducer merges overlapping (and adjacent) intervals and the second one adds up the diffs from the resulting merged ones.

答案3

得分: 1

你可以通过对这些对进行排序并检查第二个值来进行简化，然后通过计算差值来获取总和。

  1. const
  2.     nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]],
  3.     result = nums
  4.         .sort((a, b) => a[0] - b[0] || a[1] - b[1])
  5.         .reduce((r, [...a]) => {
  6.             const last = r[r.length - 1];
  7.             if (last && last[1] >= a[0]) last[1] = Math.max(last[1], a[1]);
  8.             else r.push(a);
  9.             return r;
  10.         }, [])
  11.         .reduce((s, [l, r]) => s + r - l, 0);
  13. console.log(result)
英文:

You could sort the pairs and reduce by checking the second value and then add the deltas for getting the sum.

<!-- begin snippet: js hide: false console: true babel: false -->
<!-- language: lang-js -->
const
nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]],
result = nums
.sort((a, b) => a[0] - b[0] || a1 - b1)
.reduce((r, [...a]) => {
const last = r[r.length - 1];
if (last && last1 >= a[0]) last1 = Math.max(last1, a1);
else r.push(a);
return r;
}, [])
.reduce((s, [l, r]) => s + r - l, 0);

  1. console.log(result)

<!-- end snippet -->

答案4

得分: 0

你可以将给定的二维数组的值展开到一个数组中，并对它们进行排序。
找到非重叠数组的边界值之间的差值的和，以及重叠区域内值的差值的和，两者之间的差值将是结果。

  1. const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]]
  2. let arr = []
  3. //将给定的二维数组展开
  4. nums.forEach(item => arr=[...arr,...item]);
  5. // 对两个数组进行排序
  6. arr.sort();
  7. nums.sort();
  8. let previtem, sum = 0;
  9. let min , max ;
  10. let count = 0;
  11. //循环计算非重叠值之间的差值的和
  12. nums.forEach((item,index) => {
  13.         if (index === 0) {
  14.            min = nums[0][0], max = nums[0][1]     
  15.         }
  16.         else if (!(item[0]>min && item[0]<max) && !(item[1]>min && item[1]<max))
  17.         {
  18.                 flag = 1;
  19.                 count = count + (item[0] - max);
  20.                 min = item[0];
  21.                 max = item[1];
  22.                 console.log(item,count);
  23.         }
  24.         else if (item[0]>min && item[0]<max &&  !(item[1]>min && item[1]<max)) {
  25.                 max = item[1];
  26.         }
  27. })
  29. // 循环计算重叠区域内唯一值的差值的和
  30. arr.forEach(item => {
  31.         if (previtem && item !== previtem) {
  32.                 sum=sum+(item-previtem)
  33.         }
  34.         previtem = item;
  35. })
  37. // 打印结果
  38. console.log(sum - count);
英文:

You can spread the values of given 2-D array in an array and sort both of them.
Find the sum of the differences between the edge values of non-overlapping arrays and the sum of difference of values within overlapping area and the result will be the difference between the two.

  1. const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]]
  2. let arr = []
  3. //spread given 2-D array
  4. nums.forEach(item =&gt; arr=[...arr,...item]);
  5. // Sort both arrays
  6. arr.sort();
  7. nums.sort();
  8. let previtem, sum = 0;
  9. let min , max ;
  10. let count = 0;
  11. //Loop to find sum of difference between non-overlapping values
  12. nums.forEach((item,index) =&gt; {
  13. if (index === 0) {
  14. min = nums[0][0], max = nums[0][1]     
  15. }
  16. else if (!(item[0]&gt;min &amp;&amp; item[0]&lt;max) &amp;&amp; !(item[1]&gt;min &amp;&amp; item[1]&lt;max))
  17. {
  18. flag = 1;
  19. count = count + (item[0] - max);
  20. min = item[0];
  21. max = item[1];
  22. console.log(item,count);
  23. }
  24. else if (item[0]&gt;min &amp;&amp; item[0]&lt;max &amp;&amp;  !(item[1]&gt;min &amp;&amp; item[1]&lt;max)) {
  25. max = item[1];
  26. }
  27. })
  28. // loop to find sum of difference of unique values within overlapping area
  29. arr.forEach(item =&gt; {
  30. if (previtem &amp;&amp; item !== previtem) {
  31. sum=sum+(item-previtem)
  32. }
  33. previtem = item;
  34. })
  35. //Print the result
  36. console.log(sum - count);

huangapple
  • 本文由 发表于 2022年1月6日 21:29:16
  • 转载请务必保留本文链接：https://go.coder-hub.com/70607848.html
  • algorithm
  • arrays
  • go
  • javascript
  • math
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定