MayChallenge (41) (42) | Tô Màu Ma Trận & Số Cô Đơn Trong Mảng Sắp Xếp

Số cô đơn

Bạn được cho một mảng đã sắp xếp, tất cả mọi số đều có số lặp lại của chính nó trừ 1 số duy nhất. Tìm số đó.

Ví dụ 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Ví dụ 2:

Input: [3,3,7,7,10,11,11]
Output: 10

Lưu ý: Giải pháp của bạn nên đạt O(log n)  thời gian và O(1) không gian.

Bài toán này mình đã làm một lần cách đây một tháng rồi. Nhưng thuật toán đó mất O(n) thời gian và O(1) không gian ở đây dùng bitwise.  Ban đầu nhìn thấy O(log n) mình sẽ nghĩ ngay đến tìm kiếm nhị phân.

Input: [1,1,2,3,3,4,4,8,8]
Index: [0,1,2,3,4,5,6,7,8]

Nếu mọi số đều xuất hiện 2 lần, thì nó luôn gồm 1 số chẵn và một số lẻ, và số chẵn là số đứng trước. Trong tìm kiếm nhị phân, giả sử mid = (left +right) / 2 = 4 là chẵn, giá trị 3, vậy nếu arr[5] = 3, thì chẵc chắn phần đằng trước vẫn không bị vấn đề gì, đang tuân theo quy luật số chẵn đứng trước. Còn không, chắc chắn có 1 số ở phía left có vấn đề khiến trật tự bị thay đổi.
Có một cách nữa cũng theo tư tưởng của tìm kiếm nhị phân nhưng nhìn có vẻ dễ chịu hơn, đó là two pointer. Hai con trỏ i xuất phát từ 0 và j xuất phát từ 1 sẽ nhảy 2 bước 1.

Tô màu ma trận

M image thể hiện bởi 1 ma trận hai triều, mỗi phần tử của ma trận tương ứng 1 pixcel (từ 0 tới 65535).

Cho bạn một tọa độ (sr, sc) thể hiện nơi bắt đầu (hàng và cột) sẽ được tô bằng màu mới newColor.

Quy tắc tô màu "flood fill" là, bạn đứng ở tọa đọ nêu trên, được đi 4 hướng trên dưới trái phải, nếu nó cùng màu với ô bắt đầu thì được phép thay màu. Kết quả trả về một image đã được tô màu theo yêu cầu.

Ví dụ 1:

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Giải thích: 
Điểm pixcel cuối cùng góc trái không được tô màu bởi không tuân theo quy tắc cùng màu với 4 hướng trên.

Ghi chú:

image và image[0] có độ dài trong [1, 50].

Mỗi một điểm bắt đầu thỏa mãn 0 <= sr < image.length và 0 <= sc < image[0].length.

Giá trị mỗi image[i][j] và newColor nằm trong đoạn [0, 65535].

Như một bài cũ mình đã từng làm, duyệt DFS là xong.  Độ phức tạp O(M*N). 

Hết rồi, hẹn gặp lại bạn ở các bài viết sau. Cảm ơn bạn !