1679. Max Number of K-Sum Pairs (使用 C 語言解題)

1679. Max Number of K-Sum Pairs

Solved

Medium

Topics

Companies

Hint

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

 

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

google 翻譯：

給定一個整數數組 nums 和一個整數 k。
在一次操作中，您可以從陣列中選取兩個總和等於 k 的數字並將其從陣列中刪除。

傳回可以對數組執行的最大操作數。

想法一：

先由小到大排序一次，然後跟上題相同概念，
分兩側開始往內，直到兩邊交叉為止。
一次也只動一邊，但相加等於k時兩邊同時動，並把回傳值+1。

寫法一：

int cmp(const void *a, const void *b) // qsort 比較函式
{
    return *((int *)a) - *((int *)b);
}
int maxOperations(int* nums, int numsSize, int k) {
    int left = 0; // 左邊起點
    int right = numsSize - 1; // 右邊起點
    int ret = 0, sum;
    qsort(nums, numsSize, sizeof(int), cmp); // 先由小到大排序一次
    while(left < right) { // 兩邊交叉即停止判斷 
        sum = nums[left] + nums[right];
        if(sum > k) { // 一次只動一邊
            right--;
        } else if(sum < k) { // 一次只動一邊
            left++;
        } else { // = k 兩邊同時動，並增加回傳值
            ret++;
            left++;
            right--;
        }
    }
    return ret;
}

結果一：

結果不好，再優化...

想法二：

改進排序的方法，使用快速排序法。
數組先切一半，小的放左邊，大的放右邊。
再用遞迴的方法，處理剩下的左邊，和剩下的右邊

寫法二：

void quickSort(int *nums, int size) {
    if(size <= 1) return;
    {
        int pivot = nums[size/2]; // 數組切一半，此值當關鍵值
        int *left = nums; // 左邊起點
        int *right = nums + size - 1; // 右邊起點
        while(left < right) { // 左右交叉即判斷結果
            while(*left < pivot) { // 比關鍵值小要放左邊，所以找到較大的
                left++;
            }
            while(*right > pivot) { // 比關鍵值大放右邊，所以找到較小的
                right--;
            }
            if(left <= right) { // 兩值互換，就會保持小的放左邊，大的放右邊
                int temp = *right;
                *right-- = *left;
                *left++ = temp;
            }
        }

        quickSort(nums, right - nums + 1); // 繼續處理剩下的左半邊
        quickSort(left, nums + size - left); // 繼續處理剩下的右半邊
    }
}
int maxOperations(int* nums, int numsSize, int k){
    quickSort(nums,numsSize);// 先由小到大排序一次

    int *left = nums; // 左邊起點
    int *right = nums + (numsSize - 1); // 右邊起點
    int ret = 0, sum = 0;
    while(left < right) { // 兩邊交叉即停止判斷
        sum = *left + *right;
        if(sum < k) { // 一次只動一邊
            left++;
        } else if(sum > k) { // 一次只動一邊
            right--;
        } else { // = k 兩邊同時動，並增加回傳值
            left++;
            right--;
            ret++;
        }
    }
    return ret;
}

結果二：

得到很好的結果哦...