Funkcija, kuri priima dvi surūšiuotas sveikųjų skaičių sekas. Reikia grąžinti visas pirmos sekos elementus, kurių nėra antroje. Kaip spręstumėte ir kokia būtų sudėtingumas?

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

Алгоритм:

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
}