Single Number (Easy)

Bài toán

Tiếp theo chuỗi bài về thuật toán, bài thứ 3 tôi xin giới thiệu là bài Single Number

https://leetcode.com/problems/single-number/

Tôi xin tóm tắt lại bài toán như sau:

Đề bài này yêu cầu chúng ta tìm một số nguyên duy nhất trong một mảng các số nguyên không rỗng (nums), trong đó mỗi phần tử xuất hiện hai lần trừ một số duy nhất xuất hiện một lần. Hãy đưa ra số xuất hiện một lần đấy

Ví dụ:

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Hướng giải quyết

Nhận xét

• Luôn tồn tại kết quả cuối cùng (phần tử chỉ xuất hiện 1 lần)
• Giả sử dãy được sắp xếp tăng hoặc giảm thì mình chỉ cần so sánh phần tử thứ i (từ phần tử thứ 1 trở đi) với phần tử sau nó (i+1) nếu mà bằng nhau thì bỏ qua và duyệt phần tử thứ (i+2) hoặc ngược lại thì trả ra phần tử i và dừng duyệt hoặc trong trường hợp phần tử i là phần tử cuối cùng thì cũng trả ra kết quả là chính nó.

Giải pháp

1. Sắp xếp mảng nums theo thứ tự tăng dần hoăc giảm dần.

2. Sử dụng vòng lặp for để duyệt qua từng phần tử trong mảng nums với bước nhảy là 2.

3. Trong từng lần lặp, kiểm tra xem phần tử hiện tại có bằng phần tử kế tiếp không bằng cách so sánh nums[i] với nums[i+1].

4. Nếu phần tử hiện tại không bằng phần tử kế tiếp, trả về phần tử hiện tại (vì đây là phần tử duy nhất trong mảng).

5. Nếu lặp đến phần tử cuối cùng và không tìm thấy phần tử duy nhất, trả về phần tử cuối cùng trong mảng.

   Chạy thử :

• Với nums = [1, 2, 3, 1, 3]
  • Sắp xếp tăng dần ⇒ [1, 1, 2, 3, 3]
  • Duyệt phần tử thứ nhất a[0] = 1, a[0] = a[1] ⇒ bỏ qua
  • Duyệt phần tử thứ ba (vì bước nhảy là 2) a[2] = 2, a[2] ≠ a[3] = 3 ⇒ Kết quả là a[2]

Python Code

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(0, len(nums), 2):
            if i == len(nums) - 1:
                return nums[i]
            if nums[i] != nums[i + 1]:
                return nums[i]

Link nộp bài : https://leetcode.com/problems/single-number/