Minimum Number of Operations to Make Array Continuous (LeetCode 2009)

Nguồn: LeetCode 2009 Độ khó: Khó Set Tìm kiếm nhị phân Hai con trỏ Sắp xếp

Đề bài

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

LeetCode 2009 – Minimum Number of Operations to Make Array Continuous (Số phép biến đổi ít nhất để mảng trở nên liên tục) – độ khó Hard.

Cho một mảng số nguyên nums. Trong một phép biến đổi, bạn có thể thay bất kỳ phần tử nào của nums bằng một số nguyên bất kỳ.

Mảng nums được gọi là liên tục nếu thỏa mãn cả hai điều kiện sau:

• Mọi phần tử trong nums đều đôi một khác nhau.
• Hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất của nums bằng nums.length - 1.

Ví dụ, nums = [4, 2, 5, 3] là liên tục, nhưng nums = [1, 2, 3, 5, 6] thì không liên tục.

Yêu cầu: trả về số phép biến đổi ít nhất để nums trở nên liên tục.

Ràng buộc:

• $1 \le$ nums.length $\le 10^5$
• $1 \le$ nums[i] $\le 10^9$

Ví dụ 1:

Input: nums = [4,2,5,3]
Output: 0

Giải thích: nums đã liên tục sẵn rồi.

Ví dụ 2:

Input: nums = [1,2,3,5,6]
Output: 1

Giải thích: một cách làm là đổi phần tử cuối thành 4. Mảng thu được là [1,2,3,5,4], là mảng liên tục.

Ví dụ 3:

Input: nums = [1,10,100,1000]
Output: 3

Giải thích: một cách làm là: đổi phần tử thứ hai thành 2; đổi phần tử thứ ba thành 3; đổi phần tử thứ tư thành 4. Mảng thu được là [1,2,3,4], là mảng liên tục.

2009. Minimum Number of Operations to Make Array Continuous – Hard

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

• All elements in nums are unique.
• The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make nums continuous.

Example 1:

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Example 2:

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3:

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

Constraints:

• $1 \le$ nums.length $\le 10^5$
• $1 \le$ nums[i] $\le 10^9$

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 😇.

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ác bạn chạy thử được trên máy (hoặc trang Chạy code online), mọi code trong bài đều có thêm hàm main đọc từ bàn phím theo định dạng: dòng 1 là $n$ (độ dài mảng), dòng 2 là $n$ số của nums; in ra một số là đáp án. Ví dụ 2 của đề viết thành:

5
1 2 3 5 6

và chương trình in ra 1.

Tóm tắt đề bài: cho một dãy số $a$ gồm $n$ phần tử, hãy đếm số phép biến đổi ít nhất để làm cho dãy $a$ trở thành một dãy gồm $n$ số nguyên khác nhau và liên tục (sắp xếp lại thì được $x, x+1, \ldots, x+n-1$ với một $x$ nào đó).

Mình giải thích ví dụ 2 cho bạn nào chưa hiểu đề: [1,2,3,5,6] có $n = 5$ nên ta cần đưa về 5 số liên tiếp. Nếu chọn đoạn $[1..5]$ thì các số $1, 2, 3, 5$ đã có sẵn, chỉ thiếu số $4$ ⇒ đổi số $6$ thành $4$ là xong, mất 1 phép. Không thể 0 phép vì dãy đang không liên tục. Ví dụ 3: các số $1, 10, 100, 1000$ cách nhau quá xa, đoạn 4 số liên tiếp nào cũng chỉ chứa được tối đa 1 số có sẵn ⇒ phải đổi 3 số.

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 từng phần để nhảy tới:

Cách 1ordered_set + order_of_key (cách của mình) · O(n log n)Cách 2Sắp xếp + hai con trỏ · O(n log n)

Cách 1ordered_set: đếm số giá trị khác nhau trong một đoạn – O(n log n)

Nhận xét then chốt

Dãy kết quả là $n$ số liên tiếp, tức là các số thuộc đoạn $[l .. l + n - 1]$ với một $l$ nào đó. Để biến các số trong dãy về các số thuộc đoạn $[l .. l + n - 1]$, nếu ta biết được trong đoạn $[l .. l + n - 1]$ có bao nhiêu số khác nhau đã xuất hiện trong dãy $a$ (giả sử gọi là count), thì những số này ta giữ nguyên, còn lại phải biến đổi hết.

Công thức

Với đoạn $[l .. l + n - 1]$: số phép biến đổi cần là $\ n - count$, trong đó $count$ = số giá trị khác nhau của $a$ nằm trong đoạn. Đáp án là giá trị nhỏ nhất của $n - count$ trên mọi đoạn.

Vì sao phải là số khác nhau?

Nếu dãy có hai số $5$ thì chỉ giữ lại được một số $5$ thôi, số $5$ kia bắt buộc phải đổi thành số khác (vì kết quả cần các số đôi một khác nhau). Ví dụ [1,1,1]: đoạn $[1..3]$ chỉ có 1 giá trị khác nhau ⇒ cần $3 - 1 = 2$ phép.

Vậy $l$ chọn thế nào? Ta không cần thử mọi $l$: đoạn tốt nhất luôn có thể "dịch" sang phải cho tới khi đầu trái chạm đúng một số có trong dãy mà không làm mất số nào ⇒ chỉ cần thử $l = a[i]$ với mỗi $i$, tức xét đoạn $[a[i], a[i] + n - 1]$.

Dùng ordered_set để đếm nhanh

Ta sử dụng một cấu trúc dữ liệu set $S$ có tính chất lấy được thứ tự. Đưa các phần tử trong dãy vào $S$ (set nên tự bỏ số trùng). Các bạn có thể tìm hiểu về cấu trúc dữ liệu đặc biệt này tại đây: ordered_set (GNU C++ pb_ds). Hàm hay dùng nhất là S.order_of_key(x): trả về số phần tử nhỏ hơn $x$ trong $S$, tức là thứ tự (tính từ 0) của $x$ nếu $x$ có trong $S$, chạy trong $O(\log n)$.

Giả sử ta xác định $a[i]$ là số bắt đầu của đoạn, tức ta đang xét đoạn $[a[i], a[i] + n - 1]$, ta cần đếm có bao nhiêu số khác nhau của dãy $a$ nằm trong đoạn này:

1. Dùng upper_bound(a[i] + n - 1) rồi lùi lại 1 bước để tìm ra được số lớn nhất mà $\le a[i] + n - 1$ (gọi là newvalue). Số này luôn tồn tại vì ít nhất $a[i]$ cũng $\le a[i] + n - 1$.
2. Gọi $r$ là thứ tự của newvalue, gọi $l$ là thứ tự của $a[i]$ trong tập hợp.
3. Số lượng số khác nhau có trong đoạn $[a[i], a[i] + n - 1]$ là $r - l + 1$ ⇒ số lượng số cần biến đổi là $n - (r - l + 1)$. Ta cập nhật giá trị $n - (r - l + 1)$ nhỏ nhất có thể.

Ví dụ

nums = [1,2,3,5,6], $n = 5$, $S = \{1, 2, 3, 5, 6\}$ với thứ tự $0, 1, 2, 3, 4$.
$a[i] = 1$: đoạn $[1, 5]$, số lớn nhất $\le 5$ là $5$ có thứ tự $r = 3$, $l = 0$ ⇒ có $4$ số ⇒ cần $5 - 4 = 1$ phép.
$a[i] = 3$: đoạn $[3, 7]$, số lớn nhất $\le 7$ là $6$, $r = 4$, $l = 2$ ⇒ có $3$ số ⇒ cần $2$ phép.
Lấy min mọi $i$ ⇒ đáp án 1.

Em nhập mảng rồi bấm Tiếp để xem với từng $a[i]$, "cửa sổ" giá trị $[a[i], a[i] + n - 1]$ phủ được những số nào của $S$:

nums

Ví dụ nhanh:

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

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set S;

class Solution {
public:
    int minOperations(vector<int>& nums) {
        S.clear();
        int n = (int) nums.size();
        for (int i = 0; i < n; i++) {
            S.insert(nums[i]);
        }
        int ans = n + 5;
        for (int i = 0; i < n; i++) {
            int l = S.order_of_key(nums[i]);
            int v = nums[i] + n - 1;
            ordered_set :: iterator it = S.upper_bound(v);
            it--;
            int newvalue = *it;
            int r = S.order_of_key(newvalue);
            ans = min(ans, n - (r - l + 1));
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    Solution sol;
    cout << sol.minOperations(nums);
    return 0;
}

import sys
from bisect import bisect_left, bisect_right
from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        # Python không có ordered_set: dùng mảng các giá trị khác nhau đã sắp xếp
        # order_of_key(x) chính là bisect_left(S, x)
        S = sorted(set(nums))
        n = len(nums)
        ans = n + 5
        for i in range(n):
            l = bisect_left(S, nums[i])
            v = nums[i] + n - 1
            pos = bisect_right(S, v) - 1        # vị trí số lớn nhất <= v
            newvalue = S[pos]
            r = bisect_left(S, newvalue)        # thứ tự của newvalue (= pos)
            ans = min(ans, n - (r - l + 1))
        return ans

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    nums = [int(x) for x in data[1:1 + n]]
    print(Solution().minOperations(nums))

main()

Bản Python thì sao?

Python không có sẵn ordered_set. Nhưng ở bài này tập $S$ không thay đổi sau khi nạp xong, nên ta chỉ cần một mảng đã sắp xếp, bỏ trùng: order_of_key(x) chính là bisect_left(S, x), còn "upper_bound(v) rồi lùi 1" chính là bisect_right(S, v) - 1. Logic giữ y như bản C++.

Em bấm Tiếp trong khung chạy tay dưới đây để xem từng dòng code C++ chạy (khung "Dữ liệu" vẽ mảng nums và tập $S$ đã sắp xếp, có đánh dấu $l$, $r$):

C++▶ Chạy tay từng dòng codeCách 1: ordered_set, với mỗi a[i] đếm số giá trị khác nhau trong [a[i], a[i]+n-1].

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

Dữ liệu mẫu:

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

2#include <ext/pb_ds/assoc_container.hpp>

3#include <ext/pb_ds/tree_policy.hpp>

4using namespace std;

5using namespace __gnu_pbds;

6

7#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

8ordered_set S;

9

10class Solution {

11public:

12 int minOperations(vector<int>& nums) {

13 S.clear();

14 int n = (int) nums.size();

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

16 S.insert(nums[i]);

17 }

18 int ans = n + 5;

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

20 int l = S.order_of_key(nums[i]);

21 int v = nums[i] + n - 1;

22 ordered_set :: iterator it = S.upper_bound(v);

23 it--;

24 int newvalue = *it;

25 int r = S.order_of_key(newvalue);

26 ans = min(ans, n - (r - l + 1));

27 }

28 return ans;

29 }

30};

31

32int main() {

33 int n;

34 cin >> n;

35 vector<int> nums(n);

36 for (int i = 0; i < n; i++) cin >> nums[i];

37 Solution sol;

38 cout << sol.minOperations(nums);

39 return 0;

40}

ChậmVừaNhanhRất nhanh

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

• Không gian: tập $S$ chứa tối đa $n$ phần tử ⇒ $O(n)$.
• Thời gian: nạp $n$ số vào $S$ mất $O(n \log n)$; với mỗi $i$ gọi order_of_key 2 lần và upper_bound 1 lần, mỗi lần $O(\log n)$ ⇒ tổng cộng $O(n \log n)$.

Không gian$O(n)$

Thời gian$O(n \log n)$

ordered_set chỉ có trên g++

Hai dòng #include <ext/pb_ds/...> và using namespace __gnu_pbds; là thư viện riêng của GNU g++. LeetCode, Codeforces... đều dùng được, nhưng nếu trình biên dịch của bạn là MSVC thì sẽ báo lỗi – khi đó dùng cách 2 bên dưới.

Cách 2Sắp xếp + hai con trỏ – O(n log n)

Để ý một chút: ở cách 1, tập $S$ không thay đổi sau khi nạp xong, ta chỉ hỏi thứ tự của các phần tử. Vậy thay vì ordered_set, ta có thể sắp xếp tăng dần rồi bỏ số trùng để được mảng $a$ (độ dài $m \le n$). Khi đó thứ tự của $a[i]$ chính là $i$.

Duyệt $i$ từ trái sang phải (đầu đoạn $a[i]$ tăng dần), con trỏ $j$ là vị trí đầu tiên mà $a[j] \gt a[i] + n - 1$. Vì $a[i]$ tăng nên $a[i] + n - 1$ cũng tăng ⇒ $j$ chỉ tiến, không bao giờ lùi. Số giá trị nằm trong đoạn $[a[i], a[i] + n - 1]$ là $j - i$, nên số phép cần là $n - (j - i)$.

Ý chính

Sau khi sắp xếp + bỏ trùng: đáp án $= \min_i \big(n - (j_i - i)\big)$, với $j_i$ = vị trí đầu tiên có $a[j] \gt a[i] + n - 1$. Tổng số bước tiến của $j$ không quá $m$ ⇒ phần hai con trỏ chỉ $O(n)$.

Khung minh hoạ ở cách 1 cũng thể hiện đúng ý này: các ô xanh của $S$ chính là đoạn $[i, j)$ của cách 2. Source code để các bạn tham khảo nếu làm theo hướng này:

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

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = (int) nums.size();
        vector<int> a = nums;
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());   // bỏ số trùng
        int m = (int) a.size();
        int ans = n, j = 0;
        for (int i = 0; i < m; i++) {
            // đoạn giá trị [a[i], a[i] + n - 1]
            while (j < m && a[j] <= a[i] + n - 1) j++;
            ans = min(ans, n - (j - i));                // giữ lại j - i số
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    Solution sol;
    cout << sol.minOperations(nums);
    return 0;
}

import sys
from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        a = sorted(set(nums))          # sắp xếp và bỏ số trùng
        m = len(a)
        ans = n
        j = 0
        for i in range(m):
            # đoạn giá trị [a[i], a[i] + n - 1]
            while j < m and a[j] <= a[i] + n - 1:
                j += 1
            ans = min(ans, n - (j - i))  # giữ lại j - i số
        return ans

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    nums = [int(x) for x in data[1:1 + n]]
    print(Solution().minOperations(nums))

main()

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

• Không gian: mảng sao chép $O(n)$.
• Thời gian: sắp xếp $O(n \log n)$, hai con trỏ $O(n)$ ⇒ $O(n \log n)$, hằng số nhỏ hơn cách 1 và không cần thư viện đặc biệt.

Không gian$O(n)$

Thời gian$O(n \log n)$

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên nhỏ (có nhiều số trùng), so với code vét cạn thử mọi đoạn $[L, L + n - 1]$ – khớp hết, và đúng cả 3 ví dụ của đề. Với $n = 10^5$ (tính cả thời gian đọc dữ liệu trên máy mình): cách 1 C++ khoảng 0.9 giây, cách 2 C++ khoảng 0.2 giây, hai bản Python khoảng 0.7 – 1.3 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 😇