Verilen bir sayıya eşit olan bir dizi öğeleri bir çift bul

SORU

18 Ocak 2011, Salı

Verilen bir sayıya eşit olan bir dizi öğeleri bir çift bul

Bir sayı verilen n dizisi verilmiş ve X, X eşit olan elemens (a,b), eşsiz çiftleri bulun

Aşağıdaki benim çözümdür, O(n) nLog n), ama uygun olup olmadığını emin değilim. Yorum için teşekkürler.

int main(void)
{
    int arr [10] = {1,2,3,4,5,6,7,8,9,0};
    findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
    std::sort(arr, arr len);
    int i = 0;
    int j = len -1;
    while( i < j){
        while((arr[i]   arr[j]) <= sum && i < j)
        {
            if((arr[i]   arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            i  ;
        }
        j--;
        while((arr[i]   arr[j]) >= sum && i < j)
        {
            if((arr[i]   arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            j--;
        }
    }
}

CEVAP

10 AĞUSTOS 2013, CUMARTESİ

Bu çözüm için 3 yaklaşım vardır:

. ben^>Yaklaşım 1:< / ^ br . Bunu yapmak için saf şekilde tüm kombinasyonları (n 2 seçin) kontrol etmek olacaktır. Bu kapsamlı arama O(n²).< / ^ br . < / ^ br . . ben^>Yaklaşım 2:< / ^ br . Daha iyi bir şekilde diziyi sıralamak için. Bu O(n log n) zaman alır< / ^ br . Bir dizi her biri için x sonra, ikili arama T-x için kullanın. Bu O(nlogn) alacak.< / ^ br . Yani, genel arama(n günlük n)< / ^ br . < / ^ br . . ben^>Yaklaşım 3 :< / ^ br . En iyi yolu karma tablo (sıralama olmadan) içine her öğe eklemek olacaktır. Bu O(n) sabit zaman ekleme olarak alır.< / ^ br . O zaman her x için, sadece tamamlayıcı Ey olan T-x, (1) onun bakabiliriz.< / ^ br . Genel olarak bu yaklaşımın zaman O(n).

here.Teşekkürler.

< / ^ br .

Bunu Paylaş: