遇到一个全奇数组问题，求解答
codancer 现在有 n 个正整数 a[1],a[2]…a[n]，Tom 告诉 codancer 他可以进行下列操作，选择某个偶数 x，把这 n 个数中全部等于 x 的数字除 2，Tom 想知道把这 n 个数字全部变成奇数最少需要几次这样的操作？输入一个正整数n(1<=n<=100000)，代表有n个正整数，接下来输入这n个正整数。输出 codancer 把这 n 个数字全部变成奇数的最少次数。
展开
收起
1
条回答
写回答
写回答
-
从题意及示例可以知道，应该从大到小进行操作。当除 2 后，需要快速查找是否有相等的其他数，这个需求可以使用 HashSet 代替。因此，先将n个中的偶数入HashSet，再对HashSet中元素从大到小排序，依次遍历；每个元素除 2 后从 HashSet 查找，存在则移除，计数 +1，直到该数变成奇数。最坏情况下，除 2 过程没有重复数字 因此输入：6 [40,6,40,3,20,1] 输出：4 注意 1.x=40, 数组变为[20,6,20,3,20,1] 2.x=20，数组变为[10,6,10,3,10,1] 3.x=10, 数组变为[5,6,5,3,5,1] 4.x=6，数组变为[5,3,5,3,5,1] 因此最少需要 4 次
2021-12-23 18:50:08赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
