leetcode 477题

leetcode 477 汉明距离总和

两个整数的汉明距离指的是这两个数字的二进制数对应位不同的数量。

给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间汉明距离的总和。

示例1

输入：nums = [4,14,2]
输出：6
解释：在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，2表示为 0010 。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6

示例2

输入：nums = [4,14,4]
输出：4

思路

把数组中的每个元素32位的二进制位依次扫一遍，当扫到某一位上的时候，有k个元素在这个位上的值是1，n - k 个元素在这个位置上就是 0，那么在这一位上所有两两元素的海明距离是 k*(n-k)，当把 32 位全部扫描完毕后，累加出来的海明距离就是所有两两元素的海明距离。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
function totalHammingDistance(nums) {
    let total = 0;
    let n = nums.length;
    for (let i = 0; i < 32; i++) {
        let bitCount = 0;
        for (let j = 0; j < n; j++) {
            bitCount += (nums[j] >> i) & 1;
        }
        total += bitCount * (n - bitCount);
    }
    return total;
}

复杂度分析:

时间复杂度: O(32^N)
空间复杂度：O(1)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

leetcode 477 汉明距离总和

思路

代码

CATALOG

FEATURED TAGS

FRIENDS