주어진 두 배열에서 누락된 요소를 찾습니다.

11784 단어 challengepython

문제 설명: 주어진 두 배열에서 누락된 요소를 찾는 함수를 작성하십시오.



난이도: 쉬움



테스트 사례:


  • [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로 사전에 추가합니다.

  • 사전의 모든 요소에 대해
  • 요소의 값이 0이 아닌 경우
  • 요소를 반환




  • 배타적 OR(XOR) 방법
  • 변수 결과를 0으로 초기화
  • 두 어레이를 결합합니다.
  • 결합된 배열을 통해 반복
  • 결과가 있는 모든 요소의 XOR 연산 수행
  • 누락된 요소가 될 결과를 반환합니다
  • .


  • 정렬 방법
  • 주어진 두 배열을 모두 정렬합니다.
  • 두 어레이를 동시에 반복합니다.
  • 주어진 반복에서 두 반복자의 값이 다른 경우,
  • 누락된 요소이므로 첫 번째 배열에서 요소를 반환합니다.



  • 합계 방법
  • 두 배열에 있는 모든 요소의 합을 계산합니다.
  • 첫 번째 배열에서 두 번째 배열의 합을 뺍니다.
  • 결과는 누락된 요소가 됩니다.




  • 시간 및 공간 복잡성


  • 사전 방법
  • 시간 복잡도: O(n)
  • 공간 복잡도: O(n)

  • XOR 방법
  • 시간 복잡도: O(n)
  • 공간 복잡도: O(n)

  • 정렬 방법
  • 시간 복잡도: O(nlogn)
  • 공간 복잡도: O(n)

  • 합법
  • 시간 복잡도: 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

    Original article



    행복한 코딩! 🌟

    좋은 웹페이지 즐겨찾기