牛牛爱奇数

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

输入：3,[2,2,3]
返回值：1
说明：只需做一次操作，会将其中的偶数2都变成1，满足了所有的数都是奇数的要求。

方法一:set贪心

创建一个set从大到小顺序排序，每次取出最大的值/2如果/2后还是偶数则放入set中，并统计次数,最后次数就是答案。

class Solution {
public:
    set<int, greater<int>> s;
    int oddNumber(int n, vector<int>& a) {
        // write code here
        int ans = 0;
        for(int i = 0; i < n; i ++){
            if(a[i] % 2 == 0) s.insert(a[i]); //存入set中
        }
        while(s.size()) {
            int f = *s.begin() / 2; 
            s.erase(s.begin());
            ans ++;
            if(f % 2 == 0) s.insert(f); //如果/2的值还是偶数则存入set中
        }
        return ans;
    }
};

时间复杂度: $O\left(nlogn\right)O(nlogn)$O(nlogn) set插入复杂度logn 在存入时最高会达到$O\left(nlogn\right)O(nlogn)$O(nlogn)

空间复杂度: $O\left(n\right)O(n)$O(n) set会存储最多n个元素

方法二: 哈希标记

对于每个偶数将其变成奇数并在变化过程中将数用map标记，如遇到标记的数则跳过变换，因为已经变化过了

class Solution {
public:
    unordered_map<int, bool> mp;
    int oddNumber(int n, vector<int>& a) {
        // write code here
        int res = 0;
        for(int i = 0; i < n; i ++){
            while(a[i] % 2 == 0 && !mp[a[i]]){ //如果当前数为偶数 且没有出现过
                mp[a[i]] = 1; //标记当前数
                a[i] /= 2; //当前数/2
                res ++; //更新答案
            }
        }
        return res;
    }
};

时间复杂度: 设在每次变化的过程中会达到$kk$k次不重复的 $O\left(nk\right)O(nk)$O(nk)

空间复杂度: $O\left(n\right)O(n)$O(n) 会将所有标记的数记入到map中