• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-80  評(píng)論-24  文章-0  trackbacks-0
            給定一個(gè)無(wú)序數(shù)組和一個(gè)常數(shù)k,在數(shù)組中查找指定條件的兩個(gè)數(shù),使得兩數(shù)之和等于k。
            簡(jiǎn)單的方法就不說(shuō)了,直接上比較理想的方法:
            先對(duì)數(shù)組排序,然后兩個(gè)游標(biāo),一個(gè)在數(shù)組頭,一個(gè)在數(shù)組尾,然后兩頭遍歷。
            代碼如下:

             1 int cmp(const void *a, const void *b) {
             2   return *(int *)a - *(int *)b;
             3 }
             4 
             5 struct result {
             6   int first;
             7   int second;
             8 }; 
             9 
            10 result find_two_numbers(int *a, int n, int k) {
            11   int i = 0, j = n - 1;
            12   result res = {-1, -1};
            13 
            14   if (a == NULL || n < 2) {
            15     return res;
            16   }
            17 
            18   qsort(a, n, sizeof(int), cmp);
            19   
            20   while (i < j) {
            21     if (a[i] + a[j] == k) {
            22       res.first = i;
            23       res.second = j;
            24       return res;
            25     } else if (a[i] + a[j] < k) {
            26       i++;
            27     } else {
            28       j--;
            29     }   
            30   }
            31   return res;
            32 }

            算法復(fù)雜度為O(nlogn)。

            擴(kuò)展,如果不是兩個(gè)數(shù)字而是三個(gè)數(shù)字呢?其實(shí)還是可以利用上面的方法做的,只不過(guò)得稍微轉(zhuǎn)化一下問(wèn)題,因?yàn)橐蟮氖侨齻€(gè)數(shù),而我們可以把三個(gè)數(shù)的和 a[i] + a[j] + a[r] = k轉(zhuǎn)化為兩個(gè)數(shù)的和a[j] + a[r] = k - a[i],這樣,其實(shí)只需要在上層while循環(huán)中添加一層for循環(huán),每次變化k的值為k1 = k - a[i]即可,代碼如下:

             1 struct result_three {
             2   int first;
             3   int second;
             4   int third;
             5 };
             6 
             7 result_three find_three_numbers(int *a, int n, int k) {
             8   int i, j, r;
             9   result_three res = {-1, -1, -1};
            10 
            11   if (a == NULL || n < 3) {
            12     return res;
            13   }
            14 
            15   qsort(a, n, sizeof(int), cmp);
            16 
            17   for (i = 0; i < n; ++i) {
            18     int k1 = k - a[i];
            19     j = 0, r = n - 1;
            20     while (j < r) {
            21       if (j == i) {
            22         j++;
            23         continue;
            24       }
            25       if (r == i) {
            26         r--;
            27         continue;
            28       }
            29       
            30       if (a[j] + a[r] == k1) {
            31         res.first = i;
            32         res.second = j;
            33         res.third = r;
            34         return res;
            35       } else if (a[j] + a[r] < k1) {
            36         j++;
            37       } else {
            38         r--;
            39       }
            40     }
            41   }
            42   return res;
            43 }

            上面算法復(fù)雜度很明顯為O(nlogn + n2) = O(n2)。
            現(xiàn)在問(wèn)題又變了,假如數(shù)組中不存在某兩個(gè)數(shù)的和為k,現(xiàn)在要找出某兩個(gè)數(shù)的和最接近k,那么怎么做呢?其實(shí)答案非常簡(jiǎn)單,只需要在兩個(gè)游標(biāo)i和j遍歷過(guò)程中順便用一個(gè)變量delta記錄|a[i] + a[j] - t|即可,代碼略。
            posted on 2012-09-05 22:28 myjfm 閱讀(746) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 算法基礎(chǔ)
            婷婷久久综合| 久久精品国产99国产精品导航| 久久亚洲AV无码精品色午夜麻豆| 久久人人爽人人人人片av| 久久天天躁狠狠躁夜夜2020一| 久久久噜噜噜久久中文字幕色伊伊| 久久人做人爽一区二区三区| 少妇久久久久久被弄高潮| 精品久久久久久无码专区不卡| 91麻豆精品国产91久久久久久| 伊人热热久久原色播放www| 日本WV一本一道久久香蕉| 久久精品国产99国产精偷| 三级三级久久三级久久| 91久久香蕉国产熟女线看| 亚洲国产精品成人久久| 色婷婷久久综合中文久久一本| 成人妇女免费播放久久久| 一级做a爰片久久毛片看看| 久久99免费视频| 亚洲精品乱码久久久久久按摩 | 久久久久亚洲精品中文字幕 | 青青国产成人久久91网| 中文成人无码精品久久久不卡 | 精品久久久久久综合日本| 亚洲国产香蕉人人爽成AV片久久| 色综合久久无码中文字幕| 亚洲精品无码久久毛片| 91精品国产综合久久香蕉| 好久久免费视频高清| 久久久精品2019免费观看| 狠狠色丁香久久婷婷综合_中| 精品99久久aaa一级毛片| 亚洲乱亚洲乱淫久久| 久久国产成人精品麻豆| 精品久久久久久久无码| 999久久久免费精品国产| 久久AV高清无码| 久久91综合国产91久久精品| 久久午夜伦鲁片免费无码| 无码人妻久久一区二区三区免费丨 |