2784. Check if Array is Good

題目 / Problem

中文： 給你一個整數陣列 nums。我們定義一個陣列為「好的 (good)」，當且僅當它是某個 base[n] 的排列 (permutation)。

base[n] = [1, 2, ..., n - 1, n, n]，也就是長度為 n + 1 的陣列，包含 1 到 n - 1 各一次，再加上兩個 n。例如 base[1] = [1, 1]、base[3] = [1, 2, 3, 3]。

請判斷 nums 是否為好的陣列。

English: You are given an integer array nums. The array is good if it is a permutation of base[n] for some n, where base[n] = [1, 2, ..., n-1, n, n] — an array of length n+1 containing each integer from 1 to n-1 once, plus the number n twice.

Return true if nums is good, otherwise false.

Constraints / 限制： - 1 <= nums.length <= 100 - 1 <= nums[i] <= 200

Example / 範例： - Input: nums = [1, 3, 3, 2] → Output: true （base[3] = [1, 2, 3, 3] 的排列） - Input: nums = [2, 1, 3] → Output: false （長度只有 3，但 base[3] 長度應為 4）

名詞解釋 / Glossary

• Permutation / 排列：同一組元素的不同排列順序。[1, 3, 3, 2] 與 [1, 2, 3, 3] 互為排列。Two arrays are permutations of each other if they contain exactly the same multiset of elements (same values with same counts), just possibly in a different order.
• Multiset / 多重集合：允許重複元素的集合。判斷「是否為排列」其實就是比對兩個多重集合是否相等。A set-like collection that allows duplicates; checking permutation equality is the same as checking multiset equality.
• Sorting / 排序：將陣列元素依大小重新排列。排序後，比較陣列是否相等就變得很容易。Rearranging an array so its elements are in (typically ascending) order — after sorting, two permutations of the same multiset become identical.
• qsort / 快速排序函式：C 標準函式庫提供的排序函式，需要傳入比較函式指標。qsort is C's standard library sort; it takes a pointer to a comparison function that tells it how to order two elements.
• 比較函式 / Comparator：告訴排序函式「兩元素誰大誰小」的函式。回傳負值代表前者小、正值代表前者大、零代表相等。A function returning negative/positive/zero so the sort knows the ordering between two elements.
• std::sort：C++ 標準函式庫的排序函式，預設由小到大排序。C++'s standard sort; defaults to ascending order on numeric types.
• vector<int>：C++ 中的動態陣列，可以像普通陣列一樣 v[i] 存取，但能自動管理長度。A dynamic array in C++ — access elements with v[i], and its length is managed automatically.

思路

中文： 觀察 base[n] 的結構：長度為 n + 1，最大值是 n 且出現兩次，其他 1 到 n - 1 各出現一次。因此若 nums 是好的，它的最大值 n 必須等於「陣列長度減 1」(因為長度 = n + 1)。最直覺的暴力做法是：先找最大值 n，然後檢查長度是否等於 n + 1、再檢查每個 1..n-1 是否各出現一次、n 是否出現兩次。這需要計數，可以用陣列開個計數表來統計每個值出現幾次。

但有一個更簡潔的觀察：如果把 nums 排序，好的陣列排序後一定長得像 [1, 2, 3, ..., n-1, n, n]。也就是說，排序後第 i 個位置 (0-indexed) 應該等於 i + 1，除了最後一個位置應等於 n(也就是 nums.size() - 1)。我們先排序，然後逐位置比對即可。這樣不需要計數陣列，邏輯非常直接。時間是排序的 O(k log k)，k 是長度，由於 k ≤ 100，完全足夠。

English: Look at the structure of base[n]: length n + 1, the maximum value n appears twice, and every number from 1 to n - 1 appears once. So if nums is good, its maximum must equal len(nums) - 1. The brute idea is: find the max n, check the length is n + 1, then count each value to confirm 1..n-1 appear once and n appears twice.

There is a cleaner observation: if you sort nums, a good array becomes exactly [1, 2, 3, ..., n-1, n, n]. After sorting, the value at index i (0-indexed) must be i + 1 for every position except the last, where it should also be n (the same as the previous element). Sort once, then walk through and compare each slot to its expected value. No frequency table needed, and with n ≤ 100 the O(k log k) sort is trivially fast.

逐步走查 / Walkthrough

Example: nums = [1, 3, 3, 2], length k = 4, expected n = k - 1 = 3.

Step 1 — Sort nums → [1, 2, 3, 3].

Step 2 — Walk through positions and compare with expected base[3] = [1, 2, 3, 3]:

All positions match → return true. 全部位置吻合，回傳 true。

(Contrast with nums = [2, 1, 3]: length 3, so expected n = 2. After sorting → [1, 2, 3]. Last element should be n = 2, but we see 3 → return false.)

Solution — C

// Algorithm: sort nums; a good array becomes [1, 2, ..., n-1, n, n] after sorting.
// 演算法：排序後，好的陣列會是 [1, 2, ..., n-1, n, n]。
// We check nums[i] == i+1 for all i except the last, which must equal n (= length - 1).
// 檢查除最後一格外 nums[i] == i+1，最後一格應等於 n (= 長度 - 1)。

// Comparator for qsort: returns negative/zero/positive so qsort can order ints ascending.
// qsort 用的比較函式：回傳負/零/正，讓 qsort 由小到大排序整數。
int cmp(const void *a, const void *b) {
    // *(int*)a 取出 a 指向的整數 / dereference void pointer as int
    int x = *(const int *)a;
    int y = *(const int *)b;
    // 回傳 x - y 達成升序 / returning x - y gives ascending order
    // 因為 nums[i] <= 200，x - y 不會溢位 / since values <= 200, no overflow
    return x - y;
}

bool isGood(int* nums, int numsSize) {
    // qsort 原地排序 nums / qsort sorts nums in place
    // 參數：陣列、元素個數、每個元素大小 (bytes)、比較函式
    // args: array, element count, element size in bytes, comparator
    qsort(nums, numsSize, sizeof(int), cmp);

    // 預期的 n = 長度 - 1，因為 base[n] 長度為 n + 1
    // expected n = length - 1, because base[n] has n + 1 elements
    int n = numsSize - 1;

    // 邊界：若 n == 0，長度為 1，這不可能是任何 base[n] (base[1] 長度 2)
    // edge case: n == 0 means length 1, which can't match any base[n] (base[1] has length 2)
    if (n < 1) return false;

    // 檢查前 numsSize - 1 個位置：sorted nums[i] 應等於 i + 1
    // check the first numsSize - 1 slots: sorted nums[i] should equal i + 1
    for (int i = 0; i < numsSize - 1; i++) {
        // 若不吻合，直接回傳 false / mismatch → not a good array
        if (nums[i] != i + 1) return false;
    }

    // 最後一格應等於 n (因為 n 出現兩次：在倒數第二與最後一格)
    // last slot should equal n (n appears twice: at positions n-1 and n)
    // 等價地，nums[numsSize - 1] 應等於 numsSize - 1
    // equivalently, nums[last] should equal numsSize - 1
    if (nums[numsSize - 1] != n) return false;

    // 全部通過 / all checks passed
    return true;
}

Solution — C++

// Algorithm: sort nums; a good array becomes [1, 2, ..., n-1, n, n] after sorting.
// 演算法：排序後，好的陣列形如 [1, 2, ..., n-1, n, n]。
// Then verify nums[i] == i+1 for i < size-1 and nums[size-1] == size-1.
// 接著驗證 nums[i] == i+1 (除最後一格)，且最後一格 == size - 1。

class Solution {
public:
    // vector<int>& 是「整數動態陣列的參考」，避免複製
    // vector<int>& is a reference to a dynamic int array — passed by reference to avoid copying
    bool isGood(vector<int>& nums) {
        // std::sort 預設由小到大排序，平均 O(k log k)
        // std::sort sorts ascending by default; average O(k log k)
        // nums.begin() / nums.end() 是迭代器，指向第一個元素與「最後一個之後」
        // begin()/end() are iterators marking the first element and one-past-the-last
        sort(nums.begin(), nums.end());

        // .size() 回傳元素個數，型別為 size_t (無號)；轉成 int 方便算術
        // .size() returns the element count as size_t; cast to int for arithmetic
        int k = (int)nums.size();

        // 預期的 n = 長度 - 1 / expected n = length - 1
        int n = k - 1;

        // 邊界：長度 1 不可能是任何 base[n] (base[n] 最短為 base[1] 長 2)
        // edge: length 1 cannot match any base[n] (shortest is base[1] of length 2)
        if (n < 1) return false;

        // 範圍 for 也行，但這裡需要索引，所以用傳統 for
        // could use range-for, but we need the index i, so a classic for loop is clearer
        for (int i = 0; i < k - 1; i++) {
            // 前 k - 1 格應為 1, 2, ..., n - 1, n (倒數第二格)
            // first k - 1 slots should be 1, 2, ..., n-1, n (the second-to-last slot is also n)
            if (nums[i] != i + 1) return false;
        }

        // 最後一格應等於 n (n 出現兩次的第二次)
        // last slot should equal n (the second occurrence of n)
        if (nums[k - 1] != n) return false;

        // 所有檢查通過 / all checks passed
        return true;
    }
};

複雜度 / Complexity

• Time: O(k log k) — k 是 nums 長度。瓶頸是排序；之後的線性掃描為 O(k)，被排序主導。 k is the length of nums; sorting dominates the cost, and the subsequent linear scan is O(k).
• Space: O(1) 額外空間 (不算排序內部使用的堆疊；qsort / std::sort 通常為 O(log k) 遞迴堆疊)。Extra space is constant beyond the input; sorting may use O(log k) internal recursion stack which is negligible.

Pitfalls & Edge Cases

• 長度與最大值不一致 / Length-vs-max mismatch：若 max(nums) != len(nums) - 1，就絕不可能是好的陣列。排序後比對 nums[i] == i + 1 隱含地檢查了這一點 — 若最大值錯了，最後一格的比對就會失敗。Sorting + position check implicitly enforces this; no separate check needed.
• 長度為 1 的情況 / Length 1：例如 nums = [1]。base[n] 最短的是 base[1] = [1, 1] (長度 2)，所以單元素陣列必為 false。程式碼用 n < 1 提早回傳。Single-element arrays can't be good because base[1] has length 2 — handled by the n < 1 early return.
• 元素超出 [1, n] 範圍 / Values outside [1, n]：例如 [2, 2, 3]：排序後 [2, 2, 3]，nums[0] = 2 != 1，立刻 false。值為 0 或大於 n 的情況也會在比對中被抓出。Any out-of-range or repeated wrong value triggers a position mismatch.
• 重複的非最大值 / Duplicates that aren't the max：例如 [1, 1, 2]：排序後 [1, 1, 2]，nums[1] = 1 != 2，被抓出。Duplicates of anything other than n cause a position mismatch.
• qsort 比較函式的型別轉換 / qsort comparator pointer cast：必須將 const void * 強轉成 const int * 再解參考，少寫一個 * 會比較到指標而不是值。Forgetting the cast or the dereference would compare pointer addresses instead of values — a classic C bug.
• 整數溢位 / Integer overflow in comparator：x - y 在一般情況可能溢位 (例如 INT_MIN - 1)，但題目限定 1 <= nums[i] <= 200，所以這裡安全。In general x - y can overflow for arbitrary ints, but constraints (<= 200) keep us safe here.