第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全，請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題，去搜搜看，總會(huì)有你想問(wèn)的

兩個(gè)求和問(wèn)題，但目標(biāo)在一個(gè)范圍內(nèi)

兩個(gè)求和問(wèn)題，但目標(biāo)在一個(gè)范圍內(nèi)

PHP
翻過(guò)高山走不出你 2022-10-14 15:03:12
我遇到了一個(gè)類似于舊的兩個(gè)和問(wèn)題的問(wèn)題，但不是求解一個(gè)值，它需要在一個(gè)范圍內(nèi)，我不知道如何有效地解決這個(gè)問(wèn)題。這是我的問(wèn)題的簡(jiǎn)化版本：給定一個(gè)按優(yōu)先順序排列的整數(shù)數(shù)組，找到其和位于 X 和 Y 范圍之間的前兩個(gè)整數(shù) st X <= sum <= Y（其中 X < Y 并且已知，即任意 X=20 和 Y= 40)。我已經(jīng)使用 for 循環(huán)完成了蠻力方法，但我不確定這是否是最高效的解決方案。我考慮過(guò)使用哈希表，但我不知道如何應(yīng)用它。注意：按優(yōu)先順序，我的意思是，返回滿足此條件的前兩個(gè)整數(shù)
查看完整描述

3 回答

?
拉風(fēng)的咖菲貓

TA貢獻(xiàn)1995條經(jīng)驗(yàn) 獲得超2個(gè)贊

也許這是您已經(jīng)嘗試過(guò)的蠻力方法，但我認(rèn)為這是最簡(jiǎn)單的方法。


從前兩個(gè)元素的子集開始，迭代大小增加的子集，比較子集中每個(gè)元素的值與最后一個(gè)元素的值的總和。當(dāng)你在范圍內(nèi)找到一個(gè)總和時(shí)，你就完成了。


這將根據(jù)“first”的定義找到范圍內(nèi)的第一對(duì)數(shù)字，即“具有最低最大索引的對(duì)”。


function findFirstSumInRange(int $min, int $max, array $values = []): array

{

    for ($b = 1, $n = count($values); $b < $n; $b++) {

        for ($a = 0; $a < $b; $a++) {

            if ($min <= ($sum = $values[$a] + $values[$b]) && $sum <= $max) {

                return [$values[$a], $values[$b]];

                // or return [$a => $values[$a], $b => $values[$b]]; if you need the keys as well

            }

        }

    }

    return [];

}

您可以通過(guò)跳過(guò)已經(jīng)大于范圍上限的任何值來(lái)加快速度。


function findFirstSumInRangeB(int $min, int $max, array $values = []): array

{

    for ($b = 1, $n = count($values); $b < $n; $b++) {

        if ($values[$b] < $max) { // else these sums will all be > the range because one addend is

            for ($a = 0; $a < $b; $a++) {

                if ($values[$a] < $max && $min <= ($sum = $values[$a] + $values[$b]) && $sum <= $max) {

                    return [$a => $values[$a], $b => $values[$b]];

                }

            }

        }

    }

    return [];

}

關(guān)于“性能最高的解決方案”，除非性能引起問(wèn)題，否則我寧愿追求簡(jiǎn)單而不是優(yōu)化性能。只是我的觀點(diǎn)。


查看完整回答
反對(duì) 回復(fù) 2022-10-14
?
長(zhǎng)風(fēng)秋雁

TA貢獻(xiàn)1757條經(jīng)驗(yàn) 獲得超7個(gè)贊

將每個(gè)元素添加到樹狀圖中，鍵作為元素，值作為該元素出現(xiàn)的索引列表。

在向樹形圖添加元素時(shí)，檢查是否有一個(gè)子圖，其鍵范圍從X - current_element到Y - current_element兩者都包含。如果您有子圖，您的答案是[curr_element, A[first_index_of_submap's value_of_first_key] ]


查看完整回答
反對(duì) 回復(fù) 2022-10-14
?
紅顏莎娜

TA貢獻(xiàn)1842條經(jīng)驗(yàn) 獲得超13個(gè)贊

您可以使用解決 2 sum 問(wèn)題的二進(jìn)制搜索方法，并調(diào)整您的二進(jìn)制搜索功能以在一個(gè)范圍內(nèi)搜索。像這樣的東西：


$arr = [1,2,4,6,8,14,15,17];

print_r(first_sum_in_range($arr, 25, 40));




function first_sum_in_range($array, $min, $max){

    foreach ($array as $k=>$a) {

        $b = binary_search_range($array, $a, $min, $max);

        if ($b !== false) {

            return [$a,$b];

        }

    }

}


function binary_search_range($array, $a, $min, $max) {

   $top = sizeof($array) -1;

   $bot = 0;

   while($top >= $bot) 

   {

      $p = floor(($top + $bot) / 2);

      if ($a+$array[$p] < $min) $bot = $p + 1;

      elseif ($a+$array[$p] > $max) $top = $p - 1;

      else return $array[$p];

   }

   return false;

}

輸出：


Array

(

    [0] => 8

    [1] => 17

)


查看完整回答
反對(duì) 回復(fù) 2022-10-14
  • 3 回答
  • 0 關(guān)注
  • 139 瀏覽

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

 公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)