hiho一下第211周《Total Hamming Distance》题目分析

6
1

《Total Hamming Distance》题目分析

这道题的暴力算法比较容易想到：枚举两个整数，然后看有几个二进制位不同。如果我们把32个二进制位看成是常数，那么时间复杂度是O(N^2)的。

标程的做法是按位来做。对于每一个二进制位，统计一下N个数中，有几个在这一位是0，有几个在这一位是1。假设有x个是0，y个是1，那么在这一位的产生的距离就是xy。如果我们把32个二进制位看成是常数，那么时间复杂度是O(N)的。

3 answer(s)

0

import java.util.Scanner;

public class Main { public static void main(String[] args) { Main solution = new Main(); Scanner in = new Scanner(System.in); int N = in.nextInt(); int[] nums = new int[N]; for(int i = 0; i < N; i++) nums[i] = in.nextInt(); System.out.println(solution.helper(nums)); } private int helper(int[] nums){ int bit = 1,res = 0,count = 0; //每一位去与运算 while(count < 32){ int one = 0,zero = 0; for(int x : nums){ if((bit & x) == 0) zero++; else one++; } res += one * zero; bit <<= 1; count ++; } return res; } }

  • 为什么是80呢？什么地方没有考虑到吗？

  • 答案超过整形范围

  • 阿哈，谢谢你

  • 添加评论
  • ✖reply
0

class solution{ int totalhammingdistance(vector &nums) { int res=0; int cnt=0; n=nums.size(); for(int i=0;i>1)) ++cnt; } } return cnt; } };

0

class Solution { public: int totalHammingDistance(vector& nums) { int res = 0, n = nums.size(); for (int i = 0; i < 32; ++i) { int cnt = 0; for (int num : nums) { if (num & (1 << i)) ++cnt; } res += cnt * (n - cnt); } return res; } };

write answer 切换为英文 切换为中文

转发分享

▲