来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-complement/
博主Github:https://github.com/GDUT-Rp/LeetCode
题目:对整数的二进制表示取反(0 变 1 ,1 变 0)后,再转换为十进制表示,可以得到这个整数的补数。
例如,整数 5 的二进制表示是 “101” ,取反后得到 “010” ,再转回十进制表示得到补数 2 。
给你一个整数 num ,输出它的补数。
示例 1:
输入:num = 5 输出:2 解释:5 的二进制表示为 101(没有前导零位),其补数为 010。所以你需要输出 2 。
示例 2:
输入:num = 1 输出:0 解释:1 的二进制表示为 1(没有前导零位),其补数为 0。所以你需要输出 0 。
提示:
1 <= num < 2 31 2^{31} 231
解题思路: 方法一:找二进制规律然后相减 直观想法原数字num + 其补数 + 1 = 2 n 2^n 2n (刚好比起>=的一个数)
C++Golang
func findComplement(num int) int { two_pow := 1 for i:=0; i<=32; i++ { if two_pow - 1 >= num { return two_pow - num - 1 } two_pow = two_pow << 1 } return 0 }Python
class Solution: def __init__(self): self.two_pows = [2 ** i - 1 for i in range(32)] def findComplement(self, num: int) -> int: for elem in self.two_pows: if elem >= num: return elem - num
复杂度分析
时间复杂度: O ( n ) O(n) O(n)
方法二:异或运算符找到最大的 2 n 2^n 2n,然后进行异或运算符运算即可以取补数。
C++class Solution { public: int findComplement(int num) { int temp = num, c = 0; while (temp > 0) { temp >>= 1; c = (c << 1) + 1; } return num ^ c; } };Go
func findComplement(num int) int { temp := num c := 0 for temp > 0 { temp >>= 1 c = (c << 1) + 1 } return num ^ c }Python
class Solution: def findComplement(self, num: int) -> int: temp = num c = 0 while temp > 0: temp >>= 1 c = (c << 1) + 1 return num ^ c
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)