牛牛爱奇数题解

题意：在牛牛面前放着n个数，这些数字既有奇数也有偶数，只不过牛牛对奇数情有独钟，他特别想让这些数都变成奇数。
现在牛牛获得了一种能力，他可以执行一种操作：每次选中一个偶数，然后把这些数中与该数相等的数都除以2，例如现在有一个数组为[2,2,3]，那么牛牛可以执行一次操作，使得这个数组变为[1,1,3]。
牛牛现在想知道，对于任意的n个数，他最少需要操作多少次，使得这些数都变成奇数？

时间复杂度: 空间复杂度:
解题策略：贪心
解题思路：
简明题意为：把一个数组中所有的偶数变成奇数，求最少的操作次数(每次可以选中一个数，让数组中与这个数相等的数都除以2)
解题方法有很多，最简单的方法就是暴力搜索，先将一样的偶数都记录下来，然后去除2，再记录...当然这种解法复杂度过高，在题目限制的范围内，容易超时。
为了尽量优化时间，可以采用位运算，比如使用(a & 1)判断奇数， >> 1 来做除2的运算。
一种比较好的思路是，大的数字在进行不断地操作后可能会和小的数字相等，这样就可以一起除以2，这样最终的操作次数就会减少，那么即可采用贪心思想，我们每次都选取当前最大的数字来除2，保存中间过程中的数，如果之后再次遇到这些数我们就可以直接跳过，这样就可以得到最优的结果。
根据这种思路的话，我们可以先对数组进行从大到小的排序，然后使用一个map记录中间的结果，我们可以这么写：

int solve(int n, vector<int> &a)
{
    sort(a.begin(), a.end(), greater<int>());
    map<int, bool> mp;
    mp.clear();
    int ans = 0;
    int len = a.size();
    for (int i = 0; i < len; i++)
    {
        if (mp[a[i]])
            continue;
        while (!(a[i] & 1))
            mp[a[i]] = 1, a[i] >>= 1, ans++;
    }
    return ans;
}

但其实根据以上的思想，我们还可以有一种写法，省去排序的步骤：我们可以只使用一个map，来帮助我们记录，如果当前的数不是偶数，就用map记录当前偶数，如果已经访问过就不用再除2了，如果没有访问过那么就一直除2。
将上述想法，以代码的方式实现，如下：

/**
 * 返回一个数，代表让这些数都变成奇数的最少的操作次数
 * @param n int整型 代表一共有多少数
 * @param a int整型vector 代表n个数字的值
 * @return int整型
 */
int solve(int n, vector<int> &a)
{
    // write code here
    map<int, bool> mp;
    mp.clear();
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int num = a[i];
        if (!(num & 1))
        {
            while (!(num & 1))
            {
                if (mp[num])
                    break;
                mp[num] = true;
                num >>= 1;
                ans++;
            }
        }
    }
    return ans;
}

还有一种使用set的处理方法：

class Solution {
public:
    /**
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型vector 代表n个数字的值
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        // write code here
        set<int,greater<int>>ret={a.begin(),a.end()};
        int cnt=0;
        for(auto it:ret)
            if(!(it&1))
                cnt++,ret.insert(it>>1);
        return cnt;
    }
};