Re: [問題] 程式考試時的拿捏

[Feis (坐吃山空)]

※ 引述《EdisonX (卡卡獸)》之銘言：
: 單純想討論算法。
: 1. sort (number ) , O(nlogn)
: 2. i = 0 : n-1
:    (2.1) if( number[i] ) > target ) goto end
:    (2.2) slack = target - number[i] ;
:    (2.3) search ( number + i + 1, number + n , i)
: 這種算法整體應該也還是 O(nlogn) , 概要約如下。
<deleted>
: 不知道有沒有更好的作法？ 另若是改成 (3個數之合) , (4個數之合) 為target 的話 ,
: 我也死在牆上了 XD

  假設已經排完序了，題目也保證一定有一組解，且只需要找出一組解.
  那應該是夾起來就好 ?

  auto numbers = std::array<int, 4>{2, 7, 11, 15};
  int target = 9;
  int l = 0;
  int r = numbers.size() - 1;
  int sum;
  do {
    sum = numbers[l] + numbers[r];
    if (sum > target) {
        r--;
    }  else if (sum < target) {
        l++;
    }
  } while (sum != target);
  std::cout <<"index1=" << l + 1 << ", index2=" << r + 1 << std::endl;

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.122.83.198
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1436846387.A.525.html
推 cutekid: 大推(Y)
→ EdisonX: 推 ... 這方法確實較佳。
推 cobrasgo: 有排序這個假設會不會太強了？
推 EdisonX:  @cobrasgo , 沒排序過的話做 struct 記 idx 應該不難 ,
→ EdisonX:  這篇所提的方法還是十分有效的。
推 ciphero: ㄜㄜ...怎麼到後來大家都覺得應該是有排序的~~@@
→ ciphero: 其實原題目是沒有排序的
→ ciphero: https://leetcode.com/problems/two-sum/
→ ciphero: 只不過剛好題目舉的例子看起來是有排序而已
→ EdisonX: 耶 ... 我的意思是 , 這題目就算沒排序過 , 也可以轉換成
→ EdisonX: 有排序過的 , 複雜度頂多變成 O(nlogn) , 還是有效的解法
→ Feis: 對阿. 我們只是在討論排序後的做法.
→ Feis: 另外一種就是 Hashtable
→ Feis: FYI: https://gist.github.com/feis/5fb3d820161a365add5a
推 bben900911: 除非追求超過O(nlogn) 不然假設排序過還滿OK的吧?
→ cobrasgo: 未排序的話那排序時間複雜度就是bottle neck了吧
推 cobrasgo: 用空間換時間的話，這題有O(n)的解法
推 cobrasgo: 啊我笨了，就是原po的寫法囧
→ coal511464: 面試白板題能答成這樣 那挺強的。
→ EdisonX:  白板題...好熟的面試方式...  @@