Algoritma yang cekap untuk persilangan tatasusunan di Golang

Algoritma yang cekap untuk mengira persilangan tatasusunan tertib di Golang termasuk: perbandingan satu demi satu (O(mn)), carian binari (O(m log n) atau O(n log m)), dan menggunakan peta (O(m) + n) ), dengan m dan n ialah panjang tatasusunan.

Algoritma Cekap untuk Persimpangan Tatasusunan di Golang

Mengira persilangan dua tatasusunan tertib ialah tugas biasa di Golang. Terdapat beberapa algoritma untuk menyelesaikan masalah ini, bermula daripada perbandingan satu demi satu yang mudah kepada kaedah yang cekap yang menggunakan carian binari dan struktur data lanjutan.

Bandingkan satu demi satu

Cara paling mudah ialah membandingkan setiap elemen dalam dua tatasusunan secara berurutan. Apabila elemen padanan ditemui, ia ditambah pada tatasusunan yang terhasil. Walau bagaimanapun, pendekatan ini mempunyai kerumitan masa O(mn), di mana m dan n ialah panjang dua tatasusunan. Kaedah ini boleh menjadi sangat perlahan apabila tatasusunan adalah besar.

func intersect_naive(arr1, arr2 []int) []int {
    result := []int{}
    for i := 0; i < len(arr1); i++ {
        for j := 0; j < len(arr2); j++ {
            if arr1[i] == arr2[j] {
                result = append(result, arr1[i])
            }
        }
    }
    return result
}

Binary Search

Kaedah yang lebih cekap ialah menggunakan carian binari. Untuk setiap elemen dalam tatasusunan, kami boleh menggunakan carian binari untuk menyemak sama ada ia berada dalam tatasusunan lain. Ini menghasilkan kerumitan masa O(m log n) atau O(n log m), bergantung pada saiz tatasusunan.

func intersect_binary_search(arr1, arr2 []int) []int {
    result := []int{}
    for _, v := range arr1 {
        if exists := binarySearch(arr2, v); exists {
            result = append(result, v)
        }
    }
    return result
}

func binarySearch(arr []int, target int) bool {
    left, right := 0, len(arr)-1

    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return true
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

Gunakan peta

Menggunakan peta (jadual cincang) ialah satu lagi cara yang cekap untuk mengira persimpangan. Kita boleh menyimpan elemen dalam tatasusunan sebagai kunci dalam peta dan merekodkan bilangan kali setiap elemen muncul. Kemudian kita lelaran melalui tatasusunan lain dan semak sama ada setiap elemen berada dalam peta. Jika ia wujud, kami menambahnya pada tatasusunan hasil dan mengemas kini kiraan. Ini menghasilkan kerumitan masa O(m + n), di mana m dan n ialah panjang dua tatasusunan.

func intersect_map(arr1, arr2 []int) []int {
    result := []int{}
    m := make(map[int]int)

    for _, v := range arr1 {
        m[v]++
    }

    for _, v := range arr2 {
        if count, ok := m[v]; ok {
            result = append(result, v)
            count--
            if count == 0 {
                delete(m, v)
            } else {
                m[v] = count
            }
        }
    }
    return result
}

Satu kes praktikal

Berikut ialah kes praktikal menggunakan algoritma persilangan:

arr1 := []int{1, 2, 3, 4, 5}
arr2 := []int{3, 4, 5, 6, 7}

result := intersect_map(arr1, arr2)
fmt.Println(result) // 输出：[3, 4, 5]

Dalam contoh ini, intersect_map 函数用于计算两个有序数组的交集，结果存储在 result berada dalam pembolehubah.

Atas ialah kandungan terperinci Algoritma yang cekap untuk persilangan tatasusunan di Golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!