Eine Funktion, die zwei sortierte Sequenzen von Ganzzahlen in aufsteigender Reihenfolge übernimmt. Es soll alle Elemente aus der ersten Sequenz zurückgeben, die nicht in der zweiten sind. Wie würden Sie an die Lösung herangehen und wie ist die Komplexität?

Поскольку обе последовательности отсортированы по неубыванию, оптимальным будет использовать два указателя (индекса), по одному для каждой последовательности, и идти по ним одновременно.

Алгоритм:

1. Инициализируем два индекса i и j в 0.
2. Пока i < len(A) и j < len(B):
   • Если A[i] < B[j], значит элемент A[i] отсутствует во второй последовательности, добавляем его в результат и увеличиваем i.
   • Если A[i] == B[j], элемент есть во второй последовательности, пропускаем его, увеличиваем i и j.
   • Если A[i] > B[j], увеличиваем j, чтобы догнать A[i].
3. После выхода из цикла, если остались элементы в A, добавляем их в результат, так как они точно отсутствуют во второй последовательности.

Сложность: O(n + m), где n и m — длины первой и второй последовательностей соответственно.

Пример на Go:

func differenceSorted(a, b []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            result = append(result, a[i])
            i++
        } else if a[i] == b[j] {
            i++
            j++
        } else {
            j++
        }
    }
    // Добавляем оставшиеся элементы из a
    for i < len(a) {
        result = append(result, a[i])
        i++
    }
    return result
}