gpt4 book ai didi

optimization - 汉明距离和

转载 作者:行者123 更新时间:2023-12-03 16:25:10 25 4
gpt4 key购买 nike

我开始准备面试时遇到了这个问题:

  • 给出一个整数数组
  • 现在计算数组中所有整数对以二进制表示的汉明距离之和。

  • 示例:
    given {1,2,3} or {001,010,011} (used 3 bits just to simplify)
    result= HD(001,010)+HD(001,011)+HD(010,011)= 2+1+1=4;

    唯一的优化,来自纯粹的蛮力解决方案,我知道我可以在这里使用,是在汉明距离的单独计算中,如下所示:
    int hamming_distance(unsigned x, unsigned y)
    {
    int dist;
    unsigned val;

    dist = 0;
    val = x ^ y; // XOR

    // Count the number of bits set
    while (val != 0)
    {
    // A bit is set, so increment the count and clear the bit
    dist++;
    val &= val - 1;
    }

    // Return the number of differing bits
    return dist;
    }

    解决这个问题的最佳方法是什么?

    最佳答案

    这是我的 C++ 实现,具有 O(n) 复杂度和 O(1) 空间。

    int sumOfHammingDistance(vector<unsigned>& nums) {
    int n = sizeof(unsigned) * 8;
    int len = nums.size();
    vector<int> countOfOnes(n, 0);
    for (int i = 0; i < len; i++) {
    for (int j = 0; j < n; j++) {
    countOfOnes[j] += (nums[i] >> j) & 1;
    }
    }
    int sum = 0;
    for (int count: countOfOnes) {
    sum += count * (len - count);
    }
    return sum;
    }

    关于optimization - 汉明距离和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28095890/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com