下一个更大数字的二进制表示，具有相同的1和0

本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Java
• Python3
• C#

给定一个表示正数n的二进制表示的二进制输入, 请找到大于n的最小数的二进制表示, 并且与n的二进制表示中的1和0相同。如果无法形成这样的数字, 请打印"没有更大的数字"。

即使是无符号long long int, 二进制输入可能也可能不适合。

例子：

Input : 10010
Output : 10100
Here n = (18)10 = (10010)2
next greater = (20)10 = (10100)2
Binary representation of 20 contains same number of
1's and 0's as in 18.

Input : 111000011100111110
Output :  111000011101001111

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

这个问题简单地归结为找到给定字符串的下一个排列。我们可以找到next_permutation()输入的二进制数。

以下是查找二进制字符串中下一个置换的算法。

1. 遍历二进制字符串bstr从右边。
2. 遍历时找到第一个索引一世这样bstr [i] ='0'和bstr [i + 1] ='1'。
3. 在索引" i"和" i + 1"处交换字符。
4. 由于我们需要最小的下一个值, 因此请考虑索引中的子字符串我+2结束并移动所有1个在最后的子字符串中。

下面是上述步骤的实现。

C ++

// C++ program to find next permutation in a
// binary string.
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the next greater number
// with same number of 1's and 0's
string nextGreaterWithSameDigits(string bnum)
{
     int l = bnum.size();
     int i;
     for ( int i=l-2; i>=1; i--)
     {
         // locate first 'i' from end such that
         // bnum[i]=='0' and bnum[i+1]=='1'
         // swap these value and break;
         if (bnum.at(i) == '0' &&
            bnum.at(i+1) == '1' )
         {
             char ch = bnum.at(i);
             bnum.at(i) = bnum.at(i+1);
             bnum.at(i+1) = ch;
             break ;
         }
     }
  
     // if no swapping performed
     if (i == 0)
         "no greater number" ;
  
     // Since we want the smallest next value, // shift all 1's at the end in the binary
     // substring starting from index 'i+2'
     int j = i+2, k = l-1;
     while (j < k)
     {
         if (bnum.at(j) == '1' && bnum.at(k) == '0' )
         {
             char ch = bnum.at(j);
             bnum.at(j) = bnum.at(k);
             bnum.at(k) = ch;
             j++;
             k--;
         }
  
         // special case while swapping if '0'
         // occurs then break
         else if (bnum.at(i) == '0' )
             break ;
  
         else
             j++;
  
     }
  
     // required next greater number
     return bnum;
}
  
// Driver program to test above
int main()
{
     string bnum = "10010" ;
     cout << "Binary representation of next greater number = "
          << nextGreaterWithSameDigits(bnum);
     return 0;
}

Java

// Java program to find next permutation in a
// binary string.
class GFG 
{
  
// Function to find the next greater number
// with same number of 1's and 0's
static String nextGreaterWithSameDigits( char [] bnum)
{
     int l = bnum.length;
     int i;
     for (i = l - 2 ; i >= 1 ; i--)
     {
         // locate first 'i' from end such that
         // bnum[i]=='0' and bnum[i+1]=='1'
         // swap these value and break;
         if (bnum[i] == '0' &&
         bnum[i+ 1 ] == '1' )
         {
             char ch = bnum[i];
             bnum[i] = bnum[i+ 1 ];
             bnum[i+ 1 ] = ch;
             break ;
         }
     }
  
     // if no swapping performed
     if (i == 0 )
         System.out.println( "no greater number" );
  
     // Since we want the smallest next value, // shift all 1's at the end in the binary
     // substring starting from index 'i+2'
     int j = i + 2 , k = l - 1 ;
     while (j < k)
     {
         if (bnum[j] == '1' && bnum[k] == '0' )
         {
             char ch = bnum[j];
             bnum[j] = bnum[k];
             bnum[k] = ch;
             j++;
             k--;
         }
  
         // special case while swapping if '0'
         // occurs then break
         else if (bnum[i] == '0' )
             break ;
  
         else
             j++;
  
     }
  
     // required next greater number
     return String.valueOf(bnum);
}
  
// Driver program to test above
public static void main(String[] args)
{
     char [] bnum = "10010" .toCharArray();
     System.out.println( "Binary representation of next greater number = "
         + nextGreaterWithSameDigits(bnum));
}
}
  
// This code contributed by Rajput-Ji

Python3

# Python3 program to find next permutation in a
# binary string.
  
# Function to find the next greater number
# with same number of 1's and 0's
def nextGreaterWithSameDigits(bnum):
     l = len (bnum)
     bnum = list (bnum)
     for i in range (l - 2 , 0 , - 1 ):
          
         # locate first 'i' from end such that
         # bnum[i]=='0' and bnum[i+1]=='1'
         # swap these value and break
         if (bnum[i] = = '0' and bnum[i + 1 ] = = '1' ):
             ch = bnum[i]
             bnum[i] = bnum[i + 1 ]
             bnum[i + 1 ] = ch         
             break
          
     # if no swapping performed
     if (i = = 0 ):
         return "no greater number"
          
     # Since we want the smallest next value, # shift all 1's at the end in the binary
     # substring starting from index 'i+2'
     j = i + 2
     k = l - 1
     while (j < k):
         if (bnum[j] = = '1' and bnum[k] = = '0' ):
             ch = bnum[j]
             bnum[j] = bnum[k]
             bnum[k] = ch
             j + = 1
             k - = 1
              
         # special case while swapping if '0'
         # occurs then break
         elif (bnum[i] = = '0' ):
             break
         else :
             j + = 1
      
     # required next greater number
     return bnum
  
# Driver code
bnum = "10010"
print ( "Binary representation of next greater number = " , * nextGreaterWithSameDigits(bnum), sep = "")
  
# This code is contributed by shubhamsingh10

C#

// C# program to find next permutation in a
// binary string.
using System;
  
class GFG 
{
  
// Function to find the next greater number
// with same number of 1's and 0's
static String nextGreaterWithSameDigits( char [] bnum)
{
     int l = bnum.Length;
     int i;
     for (i = l - 2; i >= 1; i--)
     {
         // locate first 'i' from end such that
         // bnum[i]=='0' and bnum[i+1]=='1'
         // swap these value and break;
         if (bnum[i] == '0' &&
         bnum[i+1] == '1' )
         {
             char ch = bnum[i];
             bnum[i] = bnum[i+1];
             bnum[i+1] = ch;
             break ;
         }
     }
  
     // if no swapping performed
     if (i == 0)
         Console.WriteLine( "no greater number" );
  
     // Since we want the smallest next value, // shift all 1's at the end in the binary
     // substring starting from index 'i+2'
     int j = i + 2, k = l - 1;
     while (j < k)
     {
         if (bnum[j] == '1' && bnum[k] == '0' )
         {
             char ch = bnum[j];
             bnum[j] = bnum[k];
             bnum[k] = ch;
             j++;
             k--;
         }
  
         // special case while swapping if '0'
         // occurs then break
         else if (bnum[i] == '0' )
             break ;
  
         else
             j++;
  
     }
  
     // required next greater number
     return String.Join( "" , bnum);
}
  
// Driver code
public static void Main(String[] args)
{
     char [] bnum = "10010" .ToCharArray();
     Console.WriteLine( "Binary representation of next greater number = "
         + nextGreaterWithSameDigits(bnum));
}
}
  
// This code is contributed by 29AjayKumar

输出如下：

Binary representation of next greater number = 10100

时间复杂度：O(n)其中n是输入中的位数。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。