---
# System prepended metadata

title: Leetcode 2499. Minimum Total Cost to Make Arrays Unequal
tags: [Greedy, hash_map, leetcode, 殘酷daily]

---

# Leetcode 2499. Minimum Total Cost to Make Arrays Unequal
###### tags: `leetcode` `殘酷daily` `Greedy` `hash_map`

[題目連結](https://leetcode.com/problems/minimum-total-cost-to-make-arrays-unequal/)

# Method Hash map
:::info
:bulb: **作法講解**:
## Concept
* If maximum count of same value is bigger than total size divided by 2, 
  => we can not make arrays unequal.
  
* If maximum count of same value is less and equal than duplicate size divided by 2.
  => we only need change the elements with same value.

* If maximum count of same value is bigger than duplicate size divided by 2.
  we need use the elements with different value.
  => the cost of smaller index is cheap than larger index.
  
  
  
## Initialize
set "max_cnt" is 0, using "max_cnt" to record maximum frequency of same value.

set "max_cnt_val" is 0, using "max_cnt_val" to record the value with maximum frequency of same value.

set "dup_cnt" is 0, using "dup_cnt" to record total count of same value.

set "output" is 0, using "output" to record the cost.

## Flow
1. we can scan each element from start to end
   if "nums1[i]" is equal with "nums2[i]"
   then do following step
   
    **a. increase the frequency of nums1[i]**
    **b. increase "dup_cnt"**
    **c. record "max_cnt" and "max_cnt_val"**
    **d. compute "output" plus by i**


2. compute "res" by 2 * "max_cnt" minus "dup_cnt"

3. we can scan each element from start to end
   when "res" is bigger than 0, and "nums1[i]" is different "nums2[i]"
   and "nums1[i]" is different "max_cnt_val" 
   and "nums2[i]" is different "max_cnt_val"
   than do following step
   
   **a. decrease "res"**
   **b. compute "output" plus by i**
:::

TC: O(N) SC: O(N)
完整程式碼
```cpp=
class Solution {
public:
    typedef long long ll;
    long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int max_cnt = 0;
        int dup_cnt = 0;
        ll output = 0;
        unordered_map<int, int> m;
        int max_cnt_val = 0;
        int res = 0;

        for(int i = 0 ; i < n ; i++) {
            if(nums1[i] == nums2[i]) {
                m[nums1[i]]++;
                if(m[nums1[i]] > max_cnt) {
                    max_cnt = m[nums1[i]];
                    max_cnt_val = nums1[i];
                }
                dup_cnt++;
                output += i;
            }
        }

        res = max_cnt - (dup_cnt - max_cnt);
        for(int i = 0 ; (i < n) && (res > 0) ; i++) {
            if((nums1[i] != nums2[i])&& (nums1[i] != max_cnt_val) && (nums2[i] != max_cnt_val)) {
                res--;
                output += i;
            }
        }
        return (res <= 0) ? output : -1;
    }
};
```
:::


