Find Original Array From Doubled Array (LeetCode 2007)

Nguồn: LeetCode 2007 Độ khó: Trung bình Tham lam Đếm phân phối Mảng đánh dấu

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

LeetCode 2007 – Find Original Array From Doubled Array (Tìm mảng gốc từ mảng nhân đôi) – độ khó Medium.

Một mảng số nguyên original được biến đổi thành một mảng nhân đôi changed bằng cách thêm vào cuối gấp đôi giá trị của mỗi phần tử trong original, rồi xáo trộn ngẫu nhiên mảng thu được.

Cho mảng changed, hãy trả về original nếu changed là một mảng nhân đôi. Nếu changed không phải là mảng nhân đôi thì trả về mảng rỗng. Các phần tử của original có thể được trả về theo thứ tự bất kỳ.

Ví dụ 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]

Giải thích: một mảng gốc có thể là [1,3,4]:

• Gấp đôi của 1 là 1 * 2 = 2.
• Gấp đôi của 3 là 3 * 2 = 6.
• Gấp đôi của 4 là 4 * 2 = 8.

Các mảng gốc khác có thể là [4,3,1] hoặc [3,1,4].

Ví dụ 2:

Input: changed = [6,3,0,1]
Output: []

Giải thích: changed không phải là mảng nhân đôi.

Ví dụ 3:

Input: changed = [1]
Output: []

Giải thích: changed không phải là mảng nhân đôi.

Ràng buộc:

• $1 \le$ changed.length $\le 10^5$
• $0 \le$ changed[i] $\le 10^5$

2007. Find Original Array From Doubled Array – Medium.

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

• 1 <= changed.length <= 10^5
• 0 <= changed[i] <= 10^5

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Tóm tắt đề bài: cho một dãy số $a$, ta tạo một dãy số $b$ bằng việc lấy từng số trong dãy $a$ và gấp đôi giá trị lên. Sau đó tạo mảng changed bằng việc ghép dãy $a$ và dãy $b$, rồi đảo thứ tự các vị trí trong dãy. Bạn hãy tái tạo lại dãy $a$ từ mảng changed, hoặc trả ra rằng không thể tái tạo (mảng rỗng).

Ví dụ: changed = [1, 2, 3, 4, 8, 6], ta sẽ tái tạo được dãy $a = [3, 1, 4]$, vì từ đó ta tạo được dãy $b = [6, 2, 8]$, ghép $a$ và $b$ vào rồi đảo thứ tự lại sẽ được đúng mảng changed. Còn Ví dụ 2 [6, 3, 0, 1]: số $0$ chỉ có thể ghép với một số $0$ khác (vì $0 \times 2 = 0$), mà mảng chỉ có một số $0$ ⇒ không tái tạo được. Ví dụ 3 có số phần tử lẻ thì chắc chắn không phải mảng nhân đôi.

Về dữ liệu vào / ra của code trong bài

Trên LeetCode các bạn chỉ cần nộp phần class Solution (cùng mảng cnt toàn cục phía trên). Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), code trong bài có thêm hàm main đọc từ bàn phím: dòng 1 là $n$ (độ dài changed), dòng 2 là $n$ số của changed; in ra mảng kết quả theo kiểu LeetCode, ví dụ [1,3,4], hoặc [] nếu không tái tạo được. Ví dụ 1 sẽ nhập là:

6
1 3 4 2 6 8

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào để nhảy tới:

Cách 1Tham lam từ số nhỏ nhất + mảng đếm · O(n + 10^5)

Cách 1Tham lam từ số nhỏ nhất + mảng đếm – O(n + 10^5)

Phương pháp giải: tham lam.

Ý tưởng

Gọi cnt[x] là số lượng số $x$ xuất hiện trong dãy.

Ta duyệt các số $x$ từ nhỏ đến lớn:

• Nếu cnt[x] > 0, đồng thời cnt[2 * x] > 0, điều này đồng nghĩa với việc số $x$ và số $2x$ cùng tồn tại trong dãy. Ta đưa số $x$ vào mảng $a$, đồng thời giảm cnt[x] đi 1 đơn vị, cnt[2 * x] đi 1 đơn vị, tức là ta dùng số $x$ cho dãy $a$ và đưa $2x$ vào dãy $b$.
• Nếu cnt[x] > 0 mà cnt[2 * x] = 0, điều này nghĩa là số $x$ thì tồn tại nhưng số $2x$ lại không tồn tại. Do đó không thể tạo được mảng $a$ thoả mãn.

Lặp lại cho tới khi cnt[x] về 0 rồi mới sang số tiếp theo.

Vì sao tham lam từ số nhỏ nhất lại đúng?

Xét số $x$ nhỏ nhất còn sót lại trong dãy (với $x \gt 0$). Nó chỉ có 2 vai trò: hoặc là số gốc (cặp với $2x$), hoặc là bản nhân đôi của $x/2$. Nhưng $x/2 \lt x$ đã được xử lý xong và không còn cái nào ⇒ $x$ bắt buộc là số gốc, phải ghép với một số $2x$. Không có $2x$ thì chắc chắn vô nghiệm. Vì vậy cách ghép là duy nhất, không cần thử nhiều khả năng.

Trường hợp đặc biệt: số 0

$0 \times 2 = 0$ nên số $0$ phải ghép với một số $0$ khác. Với $x = 0$, câu lệnh cnt[x]--; cnt[2 * x]--; thực chất trừ cnt[0] đi 2. Nếu số lượng số 0 là lẻ thì đến lượt cuối cnt[0] từ 1 sẽ thành $-1$ ⇒ đó chính là lý do code có thêm câu kiểm tra if (cnt[x] < 0 || cnt[2 * x] < 0) để trả về rỗng.

Vì sao chỉ duyệt $x$ tới $50000$? Vì $changed[i] \le 10^5$ nên số gốc $x$ phải thoả $2x \le 10^5$, tức $x \le 50000$. Các số lớn hơn $50000$ chỉ có thể là bản nhân đôi. Ngoài ra nếu $n$ lẻ thì trả về rỗng ngay.

Mình bổ sung một dòng kiểm tra

Khi kiểm thử lại code, mình thấy nếu dãy có những số $\gt 50000$ không được ghép với ai (ví dụ [1, 2, 60000, 70000]) thì code gốc trả về [1], trong khi đáp án đúng là [] – do vòng lặp chỉ chạy tới $50000$ nên không ai "kiểm tra" 2 số kia cả. Có lẽ bộ test của LeetCode không có trường hợp này nên code vẫn AC. Mình thêm ở cuối hàm: nếu ans.size() * 2 != n (còn số chưa được ghép) thì trả về mảng rỗng, cho chắc ăn.

Đánh giá độ phức tạp: $O(10^5)$ – cộng thêm $O(n)$ để đếm.

Minh hoạ mảng đếm

Em nhập mảng changed (giá trị từ 0 đến 40 cho dễ nhìn) rồi bấm Tiếp. Mỗi cột là một giá trị $x$, chiều cao cột là cnt[x]; cột cam là $x$ đang xét, cột xanh là $2x$ đang ghép cặp:

changed

Ví dụ nhanh:

Code dưới đây là code AC của mình theo tư tưởng đã trình bày ở trên, có thêm dòng kiểm tra mình vừa nói, anh em có thể tham khảo nhé:

#include <bits/stdc++.h>
using namespace std;

int cnt[100005];
class Solution {
public:
    vector<int> findOriginalArray(vector<int>& a) {
        int n = (int) a.size();
        memset(cnt, 0, sizeof(cnt));
        vector <int> ans;
        if (n % 2 == 1) {
            return ans;
        }
        for (int i = 0; i < n; i++) {
            cnt[a[i]]++;
        }
        for (int i = 0; i <= 50000; i++) {
            int x = i;
            while (cnt[x] > 0) {
                if (cnt[2 * x] > 0) {
                    cnt[x]--;
                    cnt[2 * x]--;
                    ans.push_back(x);
                }
                else {
                    ans.clear();
                    return ans;
                }
                if (cnt[x] < 0 || cnt[2 * x] < 0) {
                    ans.clear();
                    return ans;
                }
            }
        }
        if ((int) ans.size() * 2 != n) {   // còn số > 50000 chưa được ghép
            ans.clear();
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    Solution sol;
    vector<int> res = sol.findOriginalArray(a);
    cout << "[";
    for (int i = 0; i < (int) res.size(); i++) {
        if (i > 0) cout << ",";
        cout << res[i];
    }
    cout << "]";
    return 0;
}

import sys
from typing import List

class Solution:
    def findOriginalArray(self, a: List[int]) -> List[int]:
        n = len(a)
        ans = []
        if n % 2 == 1:
            return ans
        cnt = [0] * 100005
        for v in a:
            cnt[v] += 1
        for x in range(50001):
            while cnt[x] > 0:
                if cnt[2 * x] > 0:
                    cnt[x] -= 1
                    cnt[2 * x] -= 1
                    ans.append(x)
                else:
                    return []
                if cnt[x] < 0 or cnt[2 * x] < 0:
                    return []
        if len(ans) * 2 != n:           # còn số > 50000 chưa được ghép
            return []
        return ans

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:1 + n]]
    res = Solution().findOriginalArray(a)
    print("[" + ",".join(map(str, res)) + "]")

main()

Một vài chỗ cần để ý trong code:

1. Mảng cnt khai báo toàn cục, mà LeetCode gọi hàm nhiều lần cho nhiều test trên cùng một chương trình ⇒ đầu hàm phải memset(cnt, 0, sizeof(cnt)).
2. 2 * x với $x \le 50000$ tối đa là $10^5$, vẫn nằm trong mảng cnt[100005].
3. Kết quả ans ra theo thứ tự tăng dần (vì duyệt $x$ tăng dần), đề cho phép trả về theo thứ tự bất kỳ.

Em có thể chạy tay từng dòng code C++ ở khung dưới đây. Vòng for chạy tới 50000, nên những đoạn từ 3 giá trị $i$ liên tiếp trở lên mà cnt[i] đều bằng 0 (lúc đó vòng while không chạy lần nào), mình gom thành 1 bước cho đỡ dài:

C++▶ Chạy tay từng dòng codeĐếm cnt[x], duyệt x tăng dần, ghép x với 2x; thiếu 2x hoặc cnt âm thì trả về rỗng.

Dữ liệu vào (stdin) – sửa thoải mái6 1 3 4 2 6 8

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int cnt[100005];

5class Solution {

6public:

7 vector<int> findOriginalArray(vector<int>& a) {

8 int n = (int) a.size();

9 memset(cnt, 0, sizeof(cnt));

10 vector <int> ans;

11 if (n % 2 == 1) {

12 return ans;

13 }

14 for (int i = 0; i < n; i++) {

15 cnt[a[i]]++;

16 }

17 for (int i = 0; i <= 50000; i++) {

18 int x = i;

19 while (cnt[x] > 0) {

20 if (cnt[2 * x] > 0) {

21 cnt[x]--;

22 cnt[2 * x]--;

23 ans.push_back(x);

24 }

25 else {

26 ans.clear();

27 return ans;

28 }

29 if (cnt[x] < 0 || cnt[2 * x] < 0) {

30 ans.clear();

31 return ans;

32 }

33 }

34 }

35 if ((int) ans.size() * 2 != n) { // còn số > 50000 chưa được ghép

36 ans.clear();

37 }

38 return ans;

39 }

40};

41

42int main() {

43 int n;

44 cin >> n;

45 vector<int> a(n);

46 for (int i = 0; i < n; i++) cin >> a[i];

47 Solution sol;

48 vector<int> res = sol.findOriginalArray(a);

49 cout << "[";

50 for (int i = 0; i < (int) res.size(); i++) {

51 if (i > 0) cout << ",";

52 cout << res[i];

53 }

54 cout << "]";

55 return 0;

56}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Thời gian: đếm mất $O(n)$; vòng for chạy $50001$ lần, tổng số lần lặp của while bên trong không vượt quá $n / 2$ (mỗi lần ghép bỏ đi 2 số) ⇒ tổng $O(n + 10^5)$.
• Không gian: mảng đếm $10^5$ phần tử và mảng kết quả $n/2$ phần tử ⇒ $O(n + 10^5)$.

Không gian$O(n + 10^5)$

Thời gian$O(n + 10^5)$

Nếu giá trị lớn tới 10^9 thì sao?

Khi đó không mở mảng đếm được nữa. Ta vẫn dùng đúng ý tưởng tham lam: sắp xếp mảng tăng dần (hoặc dùng map đếm), duyệt từ số nhỏ nhất, mỗi số chưa bị dùng thì tìm và xoá một bản $2x$ của nó. Độ phức tạp $O(n \log n)$.

Ghi chú của mình: code C++ và Python ở trên chạy đúng 3 ví dụ của đề, và được kiểm tra với 600 bộ test ngẫu nhiên nhỏ (có nhiều số 0, số $\gt 50000$), so với code vét cạn thử mọi cách ghép cặp – khớp hết (so như tập hợp, vì đề cho trả về theo thứ tự bất kỳ). Code gốc (chưa có dòng kiểm tra ans.size() * 2 != n) sai ở những test có số $\gt 50000$ bị thừa như mình nói ở trên. Với $n = 10^5$: bản C++ chạy khoảng 0.03 giây, bản Python khoảng 0.1 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇