Una funzione che prende due sequenze ordinate in modo non decrescente di numeri interi. Deve restituire tutti gli elementi della prima sequenza che non sono nella seconda. Come affronteresti la soluzione e qual è la complessità?

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

Алгоритм:

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
}