Golang의 배열 교차를 위한 효율적인 알고리즘

Golang에서 순서 배열의 교차점을 계산하기 위한 효율적인 알고리즘에는 하나씩 비교(O(mn)), 이진 검색(O(m log n) 또는 O(n log m)) 및 맵 사용(O(m)이 포함됩니다. + n) ), 여기서 m과 n은 배열의 길이입니다.

Golang의 배열 교차를 위한 효율적인 알고리즘

두 개의 정렬된 배열의 교차를 계산하는 것은 Golang의 일반적인 작업입니다. 이 문제를 해결하기 위한 알고리즘은 간단한 일대일 비교부터 이진 검색 및 고급 데이터 구조를 활용하는 효율적인 방법에 이르기까지 다양합니다.

하나씩 비교

가장 간단한 방법은 두 배열의 각 요소를 순차적으로 비교하는 것입니다. 일치하는 요소가 발견되면 결과 배열에 추가됩니다. 그러나 이 접근 방식은 O(mn)의 시간 복잡도를 갖습니다. 여기서 m과 n은 두 배열의 길이입니다. 이 방법은 배열이 클 경우 매우 느려질 수 있습니다.

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
}

이진 검색

더 효율적인 방법은 이진 검색을 사용하는 것입니다. 배열의 각 요소에 대해 이진 검색을 사용하여 해당 요소가 다른 배열에 있는지 확인할 수 있습니다. 이로 인해 배열 크기에 따라 O(m log n) 또는 O(n log m)의 시간 복잡도가 발생합니다.

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
}

지도 사용

지도(해시 테이블)를 사용하는 것도 교차점을 계산하는 또 다른 효율적인 방법입니다. 배열의 요소를 맵의 키로 저장하고 각 요소가 나타나는 횟수를 기록할 수 있습니다. 그런 다음 다른 배열을 반복하고 각 요소가 맵에 있는지 확인합니다. 존재하는 경우 결과 배열에 추가하고 개수를 업데이트합니다. 이로 인해 O(m + n)의 시간 복잡도가 발생합니다. 여기서 m과 n은 두 배열의 길이입니다.

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
}

실용 사례

다음은 교차 알고리즘을 사용한 실제 사례입니다.

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]

이 예에서는 변수에 intersect_map 函数用于计算两个有序数组的交集，结果存储在 result가 포함되어 있습니다.

위 내용은 Golang의 배열 교차를 위한 효율적인 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!