python算法例17 下一个稀疏数

2023-12-13 15:32:04

1. 问题描述

如果一个数是稀疏数,则它的二进制表示中没有相邻的1,例如5(二进制表示为101)是稀疏数,但是6(二进制表示为110)不是稀疏数,本例将给出一个n,找出大于或等于n的最小稀疏数。

2. 问题示例

给出n=6,返回8,即下一个稀疏数是8;给出n=4,返回4,即下一个稀疏数是4;给出n=38,返回40,即下一个稀疏数是40;给出n=44,返回64,即下一个稀疏数是64。

3. 代码实现

使用贪心算法解决。从n开始,不断判断当前数是否为稀疏数,如果是则直接返回,否则将当前数加上1并重复上述步骤。

def is_sparse(n):
    """
    判断一个数是否为稀疏数
    """
    binary = bin(n)[2:]  # 转换成二进制字符串
    return '11' not in binary
    
def find_sparse_number(n):
    """
    找出大于或等于n的最小稀疏数
    """
    while True:
        if is_sparse(n):
            return n
        n += 1

# 测试
print(find_sparse_number(6))  # 输出8
print(find_sparse_number(4))  # 输出4
print(find_sparse_number(38))  # 输出40
print(find_sparse_number(44))  # 输出64

该算法时间复杂度为O(log n),因为每次判断一个数是否为稀疏数需要转换成二进制字符串,而二进制表示的位数最多为log n位。

def is_sparse(n):
    """
    判断一个数是否为稀疏数
    """
    binary = bin(n)[2:]  # 转换成二进制字符串
    for i in range(len(binary) - 1):
        if binary[i] == '1' and binary[i+1] == '1':
            return False
    return True

def next_sparse_number(n):
    """
    找出大于或者等于n的最小稀疏数
    """

    while not is_sparse(n):
        n += 1
    return n
    n += 1

# 测试示例
print(next_sparse_number(6))  # 输出 8
print(next_sparse_number(4))  # 输出 4
print(next_sparse_number(38))  # 输出 40
print(next_sparse_number(44))  # 输出 64

def next_sparse_number(n):
    binary_n = bin(n)[2:]
    length = len(binary_n)
    
    # 如果 n 本身是稀疏数,直接返回 n
    if all(binary_n[i] != '1' or binary_n[i+1] != '1' for i in range(length-1)):
        return n
    
    # 否则,找到下一个稀疏数
    i = 0
    while i < length - 1:
        if binary_n[i] == '1' and binary_n[i+1] == '1':
            n += 1  # 更新 n 的值
            binary_n = bin(n)[2:]  # 更新 binary_n
            length = len(binary_n)
            i = 0
        else:
            i += 1
    
    return n

# 测试示例
print(next_sparse_number(6))  # 输出 8
print(next_sparse_number(4))  # 输出 4
print(next_sparse_number(38))  # 输出 40
print(next_sparse_number(44))  # 输出 64

文章来源:https://blog.csdn.net/m0_62110645/article/details/134972072
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。