LeetCode1775.通過(guò)最少操作次數(shù)使數(shù)組的和相等

力扣題目鏈接：leetcode.cn/problems/eq…

給你兩個(gè)長(zhǎng)度可能不等的整數(shù)數(shù)組 nums1 和 nums2 。兩個(gè)數(shù)組中的所有值都在 1 到 6 之間（包含 1 和 6）。

每次操作中，你可以選擇 任意 數(shù)組中的任意一個(gè)整數(shù)，將它變成 1 到 6 之間 任意 的值（包含 1 和 6）。

請(qǐng)你返回使 nums1 中所有數(shù)的和與 nums2 中所有數(shù)的和相等的最少操作次數(shù)。如果無(wú)法使兩個(gè)數(shù)組的和相等，請(qǐng)返回 -1 。

示例 1：

輸入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
輸出：3
解釋：你可以通過(guò) 3 次操作使 nums1 中所有數(shù)的和與 nums2 中所有數(shù)的和相等。以下數(shù)組下標(biāo)都從 0 開始。
- 將 nums2[0] 變?yōu)?6 。 nums1 = [1,2,3,4,5,6], nums2 = [<strong>6</strong>,1,2,2,2,2] 。
- 將 nums1[5] 變?yōu)?1 。 nums1 = [1,2,3,4,5,<strong>1</strong>], nums2 = [6,1,2,2,2,2] 。
- 將 nums1[2] 變?yōu)?2 。 nums1 = [1,2,<strong>2</strong>,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

輸入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
輸出：-1
解釋：沒(méi)有辦法減少 nums1 的和或者增加 nums2 的和使二者相等。

示例 3：

輸入：nums1 = [6,6], nums2 = [1]
輸出：3
解釋：你可以通過(guò) 3 次操作使 nums1 中所有數(shù)的和與 nums2 中所有數(shù)的和相等。以下數(shù)組下標(biāo)都從 0 開始。
- 將 nums1[0] 變?yōu)?2 。 nums1 = [<strong>2</strong>,6], nums2 = [1] 。
- 將 nums1[1] 變?yōu)?2 。 nums1 = [2,<strong>2</strong>], nums2 = [1] 。
- 將 nums2[0] 變?yōu)?4 。 nums1 = [2,2], nums2 = [<strong>4</strong>] 。

提示：

• 1 <= nums1.length, nums2.length <= 105
• 1 <= nums1[i], nums2[i] <= 6

方法一：貪心 + 計(jì)數(shù)

兩個(gè)數(shù)組中的元素的初始和可能不同。為了方便，我們假設(shè)第一個(gè)數(shù)組的元素和小于第二個(gè)數(shù)組（不是的話交換兩個(gè)數(shù)組的地址即可）

那么，我們的任務(wù)就是，將第一個(gè)數(shù)組中的元素變大，或者將第二個(gè)數(shù)組中的元素減小，使得兩個(gè)數(shù)組中的元素和相等。

因?yàn)閿?shù)字的合法范圍是111到666，因此，第一個(gè)數(shù)組中，我們盡量讓小的元素優(yōu)先變成666，這樣所帶來(lái)的“和的增加”最多。

同理，第二個(gè)數(shù)組中，我們盡量讓大的元素變成111，這樣所帶來(lái)的“和的減少”最多。

因此，我們可以預(yù)處理一遍兩個(gè)數(shù)組，計(jì)算出兩個(gè)數(shù)組中“和的差值”，并統(tǒng)計(jì)兩個(gè)數(shù)組中1到6的元素的個(gè)數(shù)

然后，我們將第一個(gè)數(shù)組中的“1”變成“6”，同時(shí)將第二個(gè)數(shù)組中的“6”變成“1”，直到“沒(méi)有元素可變”或“差值小于等于0”

接著，我們將第一個(gè)數(shù)組中的“2”變成“6”，同時(shí)將第二個(gè)數(shù)組中的“5”變成“1”，直到“沒(méi)有元素可變”或“差值小于等于0”

......

這樣，我們每次修改元素，都是“盡最大努力”地減小了兩個(gè)數(shù)組中的差值，這樣就能保證每次更改能“盡大可能”地縮小差值

這就是貪心

其實(shí)不難發(fā)現(xiàn)，將第一個(gè)數(shù)組中的“1”變成“6”和將第二個(gè)數(shù)組中的“6”變成“1”所帶來(lái)的結(jié)果是等價(jià)的，因此，為了方便，我們可以直接將第二個(gè)數(shù)組中的“6”和第一個(gè)數(shù)組中的“1”統(tǒng)計(jì)到一起。

AC代碼

C++

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int s1 = accumulate(nums1.begin(), nums1.end(), 0);
        int s2 = accumulate(nums2.begin(), nums2.end(), 0);
        if (s1 > s2)
            swap(nums1, nums2);
        int times[6] = {0};
        for (int& t : nums1)
            times[t - 1]++;
        for (int& t : nums2)
            times[6 - t]++;
        int ans = 0;
        int loc = 0;
        int diff = abs(s2 - s1);
        while (diff) {
            int perChange = 6 - loc - 1;
            if (!perChange)
                break;
            int maxChange = times[loc] * perChange;
            int realChange = min(maxChange, diff);
            diff -= realChange;
            int changeTimes = realChange / perChange + (realChange % perChange != 0);
            ans += changeTimes;
            loc++;
        }
        return diff ? -1 : ans;
    }
};

以上就是C++ LeetCode1775通過(guò)最少操作次數(shù)使數(shù)組和相等的詳細(xì)內(nèi)容，更多關(guān)于C++ 最少操作數(shù)組和相等的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論