牛牛爱奇数

[编程题]牛牛爱奇数

热度指数：361 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在牛牛面前放着 $n$ 个数，这些数字既有奇数也有偶数，只不过牛牛对奇数情有独钟，他特别想让这些数都变成奇数。

现在牛牛获得了一种能力，他可以执行一种操作：每次选中一个偶数，然后把这些数中与该数相等的数都除以2，例如现在有一个数组为 $[2,2,3]$ ，那么牛牛可以执行一次操作，使得这个数组变为 $[1,1,3]$ 。

牛牛现在想知道，对于任意的 $n$ 个数，他最少需要操作多少次，使得这些数都变成奇数？

示例1

输入

3,[2,2,3]

输出

说明

只需做一次操作，会将其中的偶数2都变成1，满足了所有的数都是奇数的要求。

示例2

输入

3,[1,3,7]

输出

说明

不需要做任何操作，因为所有的数原本就是奇数。

备注:

算法知识视频讲解

牛客196305255号

利用Set不重复的特点。每次都取最大的数，除以2，丢掉或放回Set去重复。

public int solve (int n, int[] a) {
    int count=0;
	TreeSet<Integer> set=new TreeSet<>();
    for(int i:a) {
		if(i%2==0)
		set.add(i);
	}
	if(set.isEmpty())
		return 0;
	while(set.size()!=0) {
		int i=set.pollLast()/2;
		count++;
		if(i%2==0) {
		    set.add(i);
		}
	 }
	return count;
}

发表于 2020-12-05 17:16:17 回复(0)