题解 | #牛牛爱奇数#

牛牛爱奇数

http://www.nowcoder.com/practice/16ce0a2222cc4d00b3545f54eab32e94

牛牛爱奇数

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

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

方法一:set贪心

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

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(nlogn)O(nlogn)O(nlogn) set插入复杂度logn 在存入时最高会达到O(nlogn)O(nlogn)O(nlogn)

空间复杂度: O(n)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;
    }
};

时间复杂度: 设在每次变化的过程中会达到kkk次不重复的 O(nk)O(nk)O(nk)

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

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务