// Zadané jsou dvě seřazené posloupnosti celých čísel v neklesajícím pořadí. // Je třeba vrátit všechny prvky z první posloupnosti, které nejsou ve druhé. // 0 <= N <= 10^6 // -10^9 <= a[i] <= 10^9 // [1] // [2, 3, 4, 5, 6] // [1] // [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...] // [1] // [2, 3, 4, 5, 6, 7, 8] func filter(first []int, second []int) []int { res := make([]int, 0, len(first)) i, j := 0, 0 for i < len(first) && j < len(second) { if first[i] < second[j] { result = append(result, first[i]) i++ } else if first[i] > second[j] { j++ } else { i++ j++ } } for i < len(first) { result = append(result, first[i]) i++ } return result }

V uvedeném kódu v jazyce Go je chyba: proměnná result není deklarována, ale používá se res. Je nutné používat stejnou proměnnou.

Opravená verze funkce, která vrací prvky z první seřazené posloupnosti, které nejsou ve druhé:

func filter(first []int, second []int) []int {
    res := make([]int, 0, len(first))

    i, j := 0, 0

    for i < len(first) && j < len(second) {
        if first[i] < second[j] {
            res = append(res, first[i])
            i++
        } else if first[i] > second[j] {
            j++
        } else {
            i++
            j++
        }
    }

    for i < len(first) {
        res = append(res, first[i])
        i++
    }

    return res
}

Myšlenka algoritmu:

• Používáme dva ukazatele i a j k průchodu oběma posloupnostmi.
• Pokud je prvek z first menší než prvek z second, znamená to, že není ve druhé posloupnosti — přidáme ho do výsledku.
• Pokud je prvek z first větší, posuneme ukazatel j ve druhé posloupnosti.
• Pokud jsou si rovny — přeskočíme oba.
• Po skončení cyklu přidáme zbývající prvky z first.

Algoritmus pracuje v čase O(N), což je efektivní pro velké pole.