下一个更大数的二进制表示，1和0的数目相同-yiteyi-C++库

给定一个表示正数n的二进制表示的二进制输入，找到大于n的最小数的二进制表示，其1和0的数量与n的二进制表示相同。如果不能形成这样的数字，则打印“无更大的数字”。二进制输入可能是，也可能不适合无符号长整型。

null

例如：

Input : 10010Output : 10100Here n = (18)₁₀ = (10010)₂next greater = (20)₁₀ = (10100)₂Binary representation of 20 contains same number of1's and 0's as in 18.Input : 111000011100111110Output :  111000011101001111

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

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

下面是一个在二进制字符串中查找下一个排列的算法。

遍历二进制字符串 bstr 从右边。
在遍历时，找到第一个索引我这样bstr[i]=“0”和bstr[i+1]=“1”。
在索引“i”和“i+1”处交换字符。
由于我们需要最小的下一个值，从索引中考虑子串。 i+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                       

Javascript

                         <script>                       
           
                         // Javascript 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                       
                         function                                     nextGreaterWithSameDigits(bnum)                       
                         {                       
                                                 let l = bnum.length;                       
                                                 let 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'                                     )                       
                                                 {                       
                                                 let ch = bnum[i];                       
                                                 bnum[i] = bnum[i+1];                       
                                                 bnum[i+1] = ch;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 // If no swapping performed                       
                                                 if                                     (i == 0)                       
                                                 document.write(                                     "no greater number<br>"                                     );                       
                                   
                                                 // Since we want the smallest next value,                       
                                                 // shift all 1's at the end in the binary                       
                                                 // substring starting from index 'i+2'                       
                                                 let j = i + 2, k = l - 1;                       
                                                 while                                     (j < k)                       
                                                 {                       
                                                 if                                     (bnum[j] == '1                                     ' && bnum[k] == '                                     0                                     ')                       
                                                 {                       
                                                 let 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                                     (bnum).join(                                     ""                                     );                       
                         }                       
           
                         // Driver code                       
                         let bnum =                                     "10010"                                     .split(                                     ""                                     );                       
                         document.write(                                     "Binary representation of next "                                     +                       
                                                 "greater number = "                                     +                       
                                                 nextGreaterWithSameDigits(bnum));                       
           
                         // This code is contributed by rag2127                       
           
                         </script>                       

输出：

Binary representation of next greater number = 10100

时间复杂性： O（n），其中n是输入中的位数。

本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章