İki sıralanmış artan sıralı tam ədəd ardıcıllığını qəbul edən bir funksiya verilir. Birinci ardıcıllıqdan ikinci ardıcıllıqda olmayan bütün elementləri necə geri qaytararsınız və bu həllin mürəkkəbliyi nədir?

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

Алгоритм:

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
}