Une fonction qui prend deux séquences triées par ordre non décroissant d'entiers. Il faut retourner tous les éléments de la première séquence qui ne sont pas dans la seconde. Comment aborderiez-vous la solution et quelle serait la complexité?

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

Алгоритм:

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
}