Найдите недостающий элемент из данных двух массивов.

Массивы/струны проблемы кодирования (4 серии деталей)

Оператор задачи: Напишите функцию, чтобы найти недостающий элемент из данных двух массивов.

Сложный уровень: Легко

Тестовые случаи:

• [1, 2, 3, 4, 5, 6, 7],[3, 7, 2, 1, 4, 6] –> 5
• [5, 7, 7, 5, 7], [7, 7 ,5, 5] –> 7
• [9, 8, 7, 6, 5, 4, 3, 2, 1],[9, 8, 7, 5, 4, 3, 2, 1] –> 6
• [1, 2, 4, 7, 9], [7, 9, 4, 2] –> 1

Существует количество способов решить эту проблему. Ниже приведены 4 возможных решения

Алгоритм

1. Словарный метод

   • Инициализировать словарь.
   • Итерация через первый массив,
   • Если в словаре существует элемент в текущей итерации, в словаре
     • Увеличьте его значение на 1.
   • Еще,
     • Добавьте элемент как ключ и значение как 1 в словаре
   • Итерация через второй массив,
   • Если в словаре существует элемент в текущей итерации, в словаре
     • Уменьшение его значения на 1.
   • Еще,
     • Добавьте элемент как ключ и значение как 1 в словаре.
   • Для каждого элемента в словаре
     • Если значение элемента не 0
       • вернуть элемент

2. Эксклюзивный или (XOR) Метод

   • Инициализация переменной результат до 0
   • Объедините оба массива.
   • Перечислить через объединенный массив
   • Сделать Xor Работа каждого элемента с результатом
   • Вернуть результат, который будет отсутствующим элементом

3. Сортировка метода

   • Сортируйте оба данных массива.
   • Итерация над обоими массивами одновременно.
   • При данной итерации, если значение обоих итераторов отличается,
     • Верните элемент из первого массива, так как это отсутствующий элемент.

4. Сумма метода

   • Рассчитайте сумму всех элементов в обоих массивах.
   • Вычтите сумму второго массива из первого массива.
   • Результатом будет отсутствующий элемент.

Сложность времени и пространства

1. Словарный метод
   • Сложность времени: O (n)
   • Сложность пространства: O (n)
2. МЕТОД XOR
   • Сложность времени: O (n)
   • Сложность пространства: O (n)
3. Сортировка метода
   • Сложность времени: O (Nlogn)
   • Сложность пространства: O (n)
4. Сумма метода
   • Сложность времени: O (n)
   • Сложность пространства: O (1)

Код

class MissingElement(object):
    def missingElement(self, arr1, arr2):
        count = {}
        for element in arr1:
            if element in count:
                count[element] += 1
            else:
                count[element] = 1
        for element in arr2:
            if element in count:
                count[element] -= 1
            else:
                count[element] = 1
        for k in count:
            if count[k] != 0:
                return k

    def missingElement2(self, arr1, arr2):
        result = 0
        for element in arr1 + arr2:
            result ^= element
        return result

    def missingElement3(self, arr1, arr2):
        arr1.sort()
        arr2.sort()
        for ele1, ele2 in zip(arr1, arr2):
            if ele1 != ele2:
                return ele1
        return arr1[-1]

    def missingElement4(self, arr1, arr2):
        return abs(sum(arr1) - sum(arr2))

Модульный тест

import unittest
from missingElement import MissingElement


class TestMisssingElement(unittest.TestCase):
    def test_ele(self, sol):
        self.assertEqual(sol([5, 5, 7, 7], [5, 7, 7]), 5)
        self.assertEqual(sol([1, 2, 3, 4, 5, 6, 7],
                             [3, 7, 2, 1, 4, 6]), 5)
        self.assertEqual(sol([9, 8, 7, 6, 5, 4, 3, 2, 1],
                             [9, 8, 7, 5, 4, 3, 2, 1]), 6)
        print("All test cases passed")


def main():
    test = TestMisssingElement()
    element = MissingElement()
    test.test_ele(element.missingElement)
    test.test_ele(element.missingElement2)
    test.test_ele(element.missingElement3)
    test.test_ele(element.missingElement4)


if __name__ == "__main__":
    main()

GitHub Repo

Оригинальная статья

Счастливого кодирования! 🌟

Массивы/струны проблемы кодирования (4 серии деталей)

Оригинал: “https://dev.to/codewithml/find-missing-element-from-given-two-arrays-47l3”