栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

用新随机生成的值替换数组中的重复值

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

用新随机生成的值替换数组中的重复值

好的,这个问题实际上与线性序列有关。最小值为1时,请考虑以下顺序:

f(n) = 1 + 2 + ... + n - 1 + n

这样一个序列的总和等于:

f(n) = n * (n + 1) / 2

因此,对于n =
4,例如,总和为10。这意味着,如果选择4个不同的数字,则没有零且没有负数的最小总数为10。现在反过来:如果总数为10,且4个数字,则只有(1,2,3,4)的一种
组合

因此,首先您需要检查总数是否至少等于此下限。如果小于,则没有组合。如果相等,则只有一种组合。如果更高,它将变得更加复杂。

现在想象一下,您的约束总共是12个,包含4个数字。我们已经确定f(4)=10。但是,如果第一个(最低)数字为2,该怎么办?

2 + 3 + 4 + 5 = 14

因此,第一个数字不能大于1。您知道您的第一个数字。现在,您将生成一个由3个数字组成的序列,总数为11(即12-1)。

1 + 2 + 3 = 62 + 3 + 4 = 93 + 4 + 5 = 12

第二个数字必须为2,因为它不能为1。它不能为3,因为以3开头的三个数字的最小和为12,我们必须加到11。

现在我们发现两个数字加起来等于9(12-1-2),其中3是可能的最小值。

3 + 4 = 74 + 5 = 9

第三个数字可以是3或4。找到的第三个数字是固定的。两种可能的组合是:

1, 2, 3, 61, 2, 4, 5

您可以将其转换为通用算法。考虑以下递归实现:

$all = all_sequences(14, 4);echo "nAll sequences:nn";foreach ($all as $arr) {  echo implode(', ', $arr) . "n";}function all_sequences($total, $num, $start = 1) {  if ($num == 1) {    return array($total);  }  $max = lowest_maximum($start, $num);  $limit = (int)(($total - $max) / $num) + $start;  $ret = array();  if ($num == 2) {    for ($i = $start; $i <= $limit; $i++) {      $ret[] = array($i, $total - $i);    }  } else {    for ($i = $start; $i <= $limit; $i++) {      $sub = all_sequences($total - $i, $num - 1, $i + 1);      foreach ($sub as $arr) {        array_unshift($arr, $i);        $ret[] = $arr;      }    }  }  return $ret;}function lowest_maximum($start, $num) {  return sum_linear($num) + ($start - 1) * $num;}function sum_linear($num) {  return ($num + 1) * $num / 2;}

输出:

All sequences:1, 2, 3, 81, 2, 4, 71, 2, 5, 61, 3, 4, 62, 3, 4, 5

一种实现是获取所有序列并随机选择一个。这样做的好处是可以对所有可能的组合进行平均加权,这对于您正在执行的操作可能有用或不必要。

如果元素总数大或数量大,将变得笨拙,在这种情况下,可以对上述算法进行修改,以返回从

$start
$limit
而不是每个值的范围内的随机元素。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/637555.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号