Re: [問題] 程式考試時的拿捏
單純想討論算法。
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) , 概要約如下。
int number[] = {2,7,11,15} ;
int nsize = sizeof(number) / sizeof(number[0]);
int target = 9;
std::sort( number , number + nsize );
int idx1 , idx2 ; // store ans
for(int i = 0 ; i < nsize-1 ; ++i)
{
if( number[i] > target ) break; // can't find ans
slack = target - number[i] ;
int * find_rst = std::find( number + i + 1 , number + nsize , slack ) ;
if(find_rst != number + nsize) { // find ans
idx1 = i ;
idx2 = find_rst - number ;
break;
}
}
不知道有沒有更好的作法？ 另若是改成 (3個數之合) , (4個數之合) 為target 的話 ,
我也死在牆上了 XD
※ 引述《ciphero (奶油焗蛋餃...:))》之銘言：
: 問題(Question)：
: 今天試著寫了一下 LeetCode 這個網站裡的題目
: 雖然是解得出來，但是也遇到一個疑問：
: 就是效能的拿捏，與程式合理性之間該如何平衡？
: 就拿這個例子來說：
: https://leetcode.com/problems/two-sum/
: 題目意思是說輸入一個數字陣列 numbers，與一個目標數字 target，
: 如何在 numbers 中找到其中兩個數字之和，剛好等於 target。
: 舉例而言：
: Input: numbers={2, 7, 11, 15}, target=9
: 則答案就是：
: Output: index1=1, index2=2 (第1個數字(2) + 第2個數字(7) = 9)
: 題目有個前提假設：
: 輸入的陣列 numbers 裡面，必定有兩個數字之和等於 target，所以不需要考慮錯誤處理
: 所以我寫了下面第一版的程式：
: int* twoSum(int* nums, int numsSize, int target) {
: int i, j, *x;
: for(i = 1; i < numsSize; i++) {
: for(j = 0; j < i; j++) {
: if(nums[j] + nums[i] == target) {
: x = malloc(2 * sizeof(int));
: x[0] = j+1; /* index1 */
: x[1] = i+1; /* index2 */
: return x;
: }
: }
: }
: }
: 這是一個用暴力法去尋找所有兩個數字的組合，所以 time complexity = O(N^2)
: 後來覺得太慢了，就寫了下面的第二版：
: int* twoSum(int* nums, int numsSize, int target) {
: int i, diff;
: int x[200001] = {0}; /* 位置 0~200000 表示 -100000~100000 之間的數字 */
: int *y;
: for(i = 0; i < numsSize; i++)
: x[nums[i] + 100000] = i + 1; /* 儲存位置，若為 0 表示不存在 */
: for(i = 0; i < numsSize; i++) {
: diff = target - nums[i];
: if((x[diff + 100000] != 0) && (i + 1 != x[diff + 100000])) {
: y = malloc(2 * sizeof(int));
: y[0] = i + 1; /* index1 */
: y[1] = x[diff + 100000]; /* index2 */
: return y;
: }
: }
: }
: 原理是利用類似 Hash 的方法，對於有出現的數字，先儲存其位置到一個陣列中。
: 當已知某一數字，又知道 target 時，就可以相減而得知缺哪個數字，
: 再去查詢該數字是否存在，以及其位置。
: 這種方法的 time complexity 就比剛剛的第一版小很多
: but......
: 問題來了......
: 第二版的程式雖然效能快很多，但對於運算數字的大小有其限制。
: 至少我在上面的程式碼之中，是假設數字應該只會出現在 -100000~100000 的範圍之內
: 如果這樣的程式題目出現在應徵工作時，這樣寫是否恰當？
: 畢竟我覺得就工作而言，任何情況都有可能發生，
: 或者應該其實別想這麼多，只要程式能夠 work 就行？
: (至少這個版本，我在 LeetCode 裡面是有通過驗證的)
: 想請教各位高手，對於這一點的看法...
: 謝謝！
--
「自從我學了 C# , 人都變聰明 , 考試都考一百分」
「自從我學了 VB , 皮膚都變好 , 人也變漂亮了 」
「自從我學了 Java , 明顯變壯 , 個子也變高了 」
「自從我學了 C++ , 內分泌失調 , 頭都禿了... 」
< Kuso 星爺語錄 >
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.92.138
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1436837703.A.315.html
→
07/14 10:00, , 1F
07/14 10:00, 1F
→
07/14 10:01, , 2F
07/14 10:01, 2F
推
07/14 10:49, , 3F
07/14 10:49, 3F
→
07/14 11:49, , 4F
07/14 11:49, 4F
→
07/14 11:49, , 5F
07/14 11:49, 5F
→
07/14 13:01, , 6F
07/14 13:01, 6F
→
07/14 13:01, , 7F
07/14 13:01, 7F
討論串 (同標題文章)