时间戳

首页 > 解决方案 > 找出列表中的任何两个元素总和是否等于 R 中的特定值

r - 找出列表中的任何两个元素总和是否等于 R 中的特定值

问题描述

这是一个经典的面试问题。给定一个列表numbers和一个特定的值k，找出其中的任何两个元素相加时numbers是否相等。k如何r在单遍算法中解决这个问题，而不是穷举搜索？

实际上：编写r接收列表numbers和特定值的最佳函数，如果其中有两个元素，则k返回。如果没有，请返回。TRUEnumberskFALSE

标签： rlogic

解决方案

这个问题可以被描述为：是否有任何a和b在numbers，这样： a + b = k？考虑到您已经知道k，并假设实际上有两个数字相加等于k，可以假设：

a = k - b或b = k - a。

因此，通过这样做，k - numbers我们基本上将求解上述两个方程的右侧。例如：

numbers <- c(10, 12, 6, 3)和k <- 9。k - numbers会回来c(-1, -3, 3, 6)的。看看 3 和 6 是怎么出现的？

要在 R 中完成所有这些，可以定义一个函数

sum_finder <- function(numbers, k) {
    diff_sequence <- k - numbers
    condition <- any(numbers %in% diff_sequence)
    return(condition)
}

或者简单地说：

sum_finder <- function(numbers, k) {
    return(any(numbers %in% (k - numbers)))
}

编辑：出于基准测试的目的，我将在此处发布迄今为止发布的解决方案以及使用microbenchmark::microbenchmark().

# as posted by @eduardokapp
function1 <- function(numbers, k) {
    any(numbers %in% (k - numbers))
}

# as posted by @AnilGoyal
function2 <- function(numbers, k) {
    any(apply(outer(numbers, numbers, `+`), 1, function(x){x == k}))
}

# Performance Comparison
numbers <- sample(500, 500)
k <- sample(500, 1)
microbenchmark::microbenchmark(
   function1(numbers, k),
   function2(numbers, k)
)

性能比较

单位：微秒

表达式 分钟 lq 意思是 中位数 乌克 最大限度 内瓦尔
函数1（数字，k） 13.651 21.277 39.58225 27.4485 40.1905 277.256 100
函数2（数字，k） 5061.088 5805.186 10971.04516 7571.6030 13316.1325 47782.874 100

推荐阅读