最接近的数 牛客网 程序员面试金典 C++ Python

最接近的数 牛客网 程序员面试金典 C++ Python

题目描述

有一个正整数，请找出其二进制表示中1的个数相同、且大小最接近的那两个数。(一个略大，一个略小)

给定正整数int x，请返回一个vector，代表所求的两个数（小的在前）。保证答案存在。

测试样例：

2

返回：[1,4]

C++

class CloseNumber { public: //run:3ms memory:504k vector<int> getCloseNumber(int x) { vector<int> ret; int count = getOneCount(x); int lower = x-1; int larger = x+1; while(getOneCount(lower) != count) lower--; ret.push_back(lower); while(getOneCount(larger) != count) larger++; ret.push_back(larger); return ret; } int getOneCount(int x){ int count = 0; for(;x;count++) x= x&(x-1); return count; } };

Python

class CloseNumber: #run:38ms memory:5732k def getCloseNumber(self, x): ret = [] lower = x - 1 larger = x + 1 count = self.getOneCount(x) while self.getOneCount(lower) != count: lower -= 1 ret.append(lower) while self.getOneCount(larger) != count: larger += 1 ret.append(larger) return ret def getOneCount(self,x): count = 0; while x: count += 1 x = x & (x -1) return count

 

转载于:https://www.cnblogs.com/vercont/p/10210317.html