LeetCode Ts-2869. Minimum Operations to Collect Elements

    AllenLi
    CodingLeetCode Js-Array

    You are given an array nums of positive integers and an integer k.
    In one operation, you can remove the last element of the array and add it to your collection.
    Return the minimum number of operations needed to collect elements 1, 2, …, k.

    你給予一個正整數的陣列 nums 和一個整數 k。
在一次的操作中，你可以移除陣列的最後一個元素，並添加到你的集合。
回傳需要收集元素 1, 2, 3, ... k 的最小數量操作。

    Example 1:

    Input: nums = [3,1,5,4,2], k = 2
Output: 4
Explanation: After 4 operations, we collect elements 2, 4, 5, and 1, in this order. Our collection contains elements 1 and 2. Hence, the answer is 4.

    Example 2:

    Input: nums = [3,1,5,4,2], k = 5
Output: 5
Explanation: After 5 operations, we collect elements 2, 4, 5, 1, and 3, in this order. Our collection contains elements 1 through 5. Hence, the answer is 5.

    Example 3:

    Input: nums = [3,2,5,3,1], k = 3
Output: 4
Explanation: After 4 operations, we collect elements 1, 3, 5, and 2, in this order. Our collection contains elements 1 through 3. Hence, the answer is 4.

    Solution:
    根據題目要求，我們從陣列的尾端開始遍歷，
    在遍歷的過程中收集所有小於或等於 k 的元素，
    並將符合條件的元素加入一個 Set 中（這裡要確保不重複）。
    同時計算我們遍歷的次數。
    當 Set 中的元素個數等於 k 時，表示我們已經收集到從 1 到 k 的所有數值，
    此時回傳目前的遍歷次數即可。
    若遍歷結束仍未達到 k，則回傳總遍歷次數。
    [3, 1, 5, 4, 2]
    k = 2(1 ~ 2) pop 2, add {2}
    k = 2(1 ~ 2) pop 4, add {2, 4}
    k = 2(1 ~ 2) pop 5, add {2, 4, 5}
    k = 2(1 ~ 2) pop 1, add {2, 4, 5, 1}

    Code 1: BigO(n)

    function minOperations(nums: number[], k: number): number {
    const set: Set = new Set();
    let count: number = 0;
    for (let i = nums.length - 1; i >= 0; i--) {
        const value: number = nums[i];
        if (value <= k) set.add(value);
        count++;
        if (set.size === k) return count;        
    }
    return count;
};

    FlowChart:
    Example 1

    Input: nums = [3,1,5,4,2], k = 2

value 2, set Set(1) { 2 }, count 1
value 4, set Set(1) { 2 }, count 2
value 5, set Set(1) { 2 }, count 3
value 1, set Set(2) { 2, 1 }, count 4
return count; // 4

    Example 2

    Input: nums = [3,1,5,4,2], k = 5

value 2, set Set(1) { 2 }, count 1
value 4, set Set(2) { 2, 4 }, count 2
value 5, set Set(3) { 2, 4, 5 }, count 3
value 1, set Set(4) { 2, 4, 5, 1 }, count 4
value 3, set Set(5) { 2, 4, 5, 1, 3 }, count 5
return count; // 5

    Example 3

    Input: nums = [3,2,5,3,1], k = 3

value 1, set Set(1) { 1 }, count 1
value 3, set Set(2) { 1, 3 }, count 2
value 5, set Set(2) { 1, 3 }, count 3
value 2, set Set(3) { 1, 3, 2 }, count 4
return count; // 4

    Related Posts