iT邦幫忙

0

如何設計陣列搜尋的程式?

若要寫一個程式:
一個陣列含有n-1個元素,這些元素是n個連續整數中少其中一個(如:2,3,5,6,7,8,連續整數範圍是2-8,且少了4)
要怎麼寫出最快的搜尋方法的程式?(空間複雜度希望為O(1))

我的想法是先排序再找出缺的,可是這樣好像不是最快的...
請問大家有更好的辦法嗎?一起討論吧!!謝謝><

1
海綿寶寶
iT邦大神 1 級 ‧ 2021-01-20 11:16:37
最佳解答

實作樓上各位的「梯形演算法」如下

#include <stdio.h>

int main()
{
    int arr[] = {2,3,5,6,7,8};
    size_t sz = sizeof(arr) / sizeof(int);
    int answer, sum=0;
    int topline=sz, baseline=0, height=sz+1;

    //找出上底和下底,順便把所有值加起來
    for (int i=0;i<sz;i++) {
        if (arr[i]<topline) { topline = arr[i]; }
        if (arr[i]>baseline) { baseline = arr[i]; }
        sum = sum + arr[i];
    }
    answer = (topline+baseline)*height/2 - sum;

    printf("The answer is %d.\n", answer);
    
    return 0;
}
看更多先前的回應...收起先前的回應...

其實說真的。如果要for的話。
就直接用for找出來就好了。
不用這樣計算才對的。

我是依不用for來想的。
要for的話就很簡單了。

jocelynnn iT邦新手 5 級 ‧ 2021-01-20 12:02:35 檢舉

謝謝!!我看好久><(程式真的不熟!)
但中間那邊不太了解:
for (int i=0;i<asize;i++) {
arrB[value2index(arr[i])] = arr[i];

這邊的處理是怎麼做到-1就是缺項的,
是指index再指向arrayB,對應arrayA的缺項嗎?

一次回覆兩位
我已經改答案了
原本那個(空間複雜度)O(2n) 的程式
就算了
/images/emoticon/emoticon25.gif

jocelynnn iT邦新手 5 級 ‧ 2021-01-20 12:12:54 檢舉

XDDD謝謝你!!!

看錯了,是空間複雜度 O(1)
自刪

Leetcode 的類似題目有四種解法
你的「排序」是第一種

jocelynnn iT邦新手 5 級 ‧ 2021-01-20 13:02:13 檢舉

我不知道leetcode
剛剛馬上去註冊了!!竟然有這麼好的網站?

6
chichi
iT邦新手 5 級 ‧ 2021-01-20 08:40:02

利用陣列長度算加總(梯形公式),在減去陣列裡存在的元素

按三個
/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif/images/emoticon/emoticon12.gif

jocelynnn iT邦新手 5 級 ‧ 2021-01-20 11:05:56 檢舉

謝謝!!我懂你的意思了!

沒注意到跟我的解法一樣。
我確實是用梯型公式處理的。

1
鬼王很慘
iT邦新手 4 級 ‧ 2021-01-20 10:33:25

已經連續整數就不需要再排序了吧?

for (int i = 0; i < array.length; i++) {
    if (array[i] + 1 != array[i+1]) {
        value = array[i] + 1;
    }
}

感覺至少還是要O(n)

jocelynnn iT邦新手 5 級 ‧ 2021-01-20 11:06:42 檢舉

喔喔對!我沒注意不需排序!!
謝謝!!

1

(最小值+最大值)*(最大值-最小值+1)/2 - 目前陣列總合

依你的例子

    (2+8)*(8-2+1)/2  - (2+3+5+6+7+8)
    10*7/2 - 31
    35 -31
    = 4

不過這只適合缺一個。缺2個以上,就得用其它算法了
之前有學過,好像要用一下三角函數還是對數??
只是一時之間想不起來了。

jocelynnn iT邦新手 5 級 ‧ 2021-01-20 11:07:31 檢舉

謝謝!!看你們解完發現其實不難!!我懂了?

我要發表回答

立即登入回答