dsal 通过排列数字得到的最大回文数

通过排列数字得到的最大回文数

原文：https://www.geeksforgeeks.org/largest-palindromic-number-permuting-digits/

给定N（非常大），任务是打印通过排列N的数字获得的最大回文数。如果不可能生成回文数，则打印适当的消息。

示例：

Input : 313551
Output : 531135
Explanations : 531135 is the largest number 
which is a palindrome, 135531, 315513 and other 
numbers can also be formed but we need the highest 
of all of the palindromes. 

Input : 331
Output : 313

Input : 3444
Output : Pallindrome cannot be formed

朴素的方法：朴素的方法将尝试所有可能的排列，并打印出此类组合中最大的一个回文。

有效方法：一种有效方法是使用贪婪算法。由于数字较大，因此请将数字存储在字符串中。将给定数字中每个数字的出现次数存储在映射中。检查是否可能生成回文。如果可以将给定数字的数字重新排列以生成回文，则可以使用贪婪方法获得该数字。检查是否存在每个数字（9 到 0），并将每个可用数字放在前面和后面。 最初，front指针将在索引 0 处，因为最大的数字将被放在第一位，以使数字最大。 每执行一步，将front指针向前移动 1 个位置。如果该数字出现奇数次，则将一个数字放在中间，其余偶数次的数字放在front和back。重复map[digit] / 2次。在front和back放置出现了偶数次的特定数字后，将front指针向前移动一步。继续直到map[digit]为 0。贪婪地完成数字放置后，字符数组将具有最大的回文数字。

在最坏的情况下，如果数字在每个位置都包含相同的数字，则时间复杂度将为O(10 * (字符串的长度/ 2))。

下面是上述想法的实现：

C++

// CPP program to print the largest palindromic 
// number by permuting digits of a number 
#include <bits/stdc++.h> 
using namespace std; 

// function to check if a number can be 
// permuted to form a palindrome number 
bool possibility(unordered_map<int, int> m, 
                 int length, string s) 
{ 
    // counts the occurrence of number which is odd 
    int countodd = 0; 
    for (int i = 0; i < length; i++) { 

        // if occurrence is odd 
        if (m[s[i] - '0'] & 1) 
            countodd++; 

        // if number exceeds 1 
        if (countodd > 1) 
            return false; 
    } 

    return true; 
} 

// function to print the largest palindromic number 
// by permuting digits of a number 
void largestPalindrome(string s) 
{ 

    // string length 
    int l = s.length(); 

    // map that marks the occurrence of a number 
    unordered_map<int, int> m; 
    for (int i = 0; i < l; i++) 
        m[s[i] - '0']++; 

    // check the possibility of a palindromic number 
    if (possibility(m, l, s) == false) { 
        cout << "Palindrome cannot be formed"; 
        return; 
    } 

    // string array that stores the largest 
    // permuted palindromic number 
    char largest[l]; 

    // pointer of front 
    int front = 0; 

    // greedily start from 9 to 0 and place the 
    // greater number in front and odd in the 
    // middle 
    for (int i = 9; i >= 0; i--) { 

        // if the occurrence of number is odd 
        if (m[i] & 1) { 

            // place one odd occurring number 
            // in the middle 
            largest[l / 2] = char(i + 48); 

            // decrease the count 
            m[i]--; 

            // place the rest of numbers greedily 
            while (m[i] > 0) { 
                largest[front] = char(i + 48); 
                largest[l - front - 1] = char(i + 48); 
                m[i] -= 2; 
                front++; 
            } 
        } 
        else { 

            // if all numbers occur even times, 
            // then place greedily 
            while (m[i] > 0) { 

                // place greedily at front 
                largest[front] = char(i + 48); 
                largest[l - front - 1] = char(i + 48); 

                // 2 numbers are placed, so decrease the count 
                m[i] -= 2; 

                // increase placing position 
                front++; 
            } 
        } 
    } 

    // print the largest string thus formed 
    for (int i = 0; i < l; i++) 
        cout << largest[i]; 
} 

// Driver Code 
int main() 
{ 
    string s = "313551"; 
    largestPalindrome(s); 
    return 0; 
}

Python3

# Python3 program to print the largest palindromic  
# number by permuting digits of a number  
from collections import defaultdict 

# Function to check if a number can be  
# permuted to form a palindrome number  
def possibility(m, length, s):  

    # counts the occurrence of  
    # number which is odd  
    countodd = 0
    for i in range(0, length):  

        # if occurrence is odd  
        if m[int(s[i])] & 1:  
            countodd += 1

        # if number exceeds 1  
        if countodd > 1:  
            return False

    return True

# Function to print the largest palindromic  
# number by permuting digits of a number  
def largestPalindrome(s):  

    # string length  
    l = len(s)  

    # map that marks the occurrence of a number  
    m = defaultdict(lambda:0) 
    for i in range(0, l):  
        m[int(s[i])] += 1

    # check the possibility of a  
    # palindromic number  
    if possibility(m, l, s) == False: 
        print("Palindrome cannot be formed")  
        return

    # string array that stores the largest  
    # permuted palindromic number  
    largest = [None] * l  

    # pointer of front  
    front = 0

    # greedily start from 9 to 0 and place the  
    # greater number in front and odd in the middle  
    for i in range(9, -1, -1):  

        # if the occurrence of number is odd  
        if m[i] & 1: 

            # place one odd occurring number  
            # in the middle  
            largest[l // 2] = chr(i + 48)  

            # decrease the count  
            m[i] -= 1

            # place the rest of numbers greedily  
            while m[i] > 0:  
                largest[front] = chr(i + 48)  
                largest[l - front - 1] = chr(i + 48)  
                m[i] -= 2
                front += 1

        else: 

            # if all numbers occur even times,  
            # then place greedily  
            while m[i] > 0:  

                # place greedily at front  
                largest[front] = chr(i + 48)  
                largest[l - front - 1] = chr(i + 48)  

                # 2 numbers are placed,  
                # so decrease the count  
                m[i] -= 2

                # increase placing position  
                front += 1

    # print the largest string thus formed  
    for i in range(0, l):  
        print(largest[i], end = "")  

# Driver Code  
if __name__ == "__main__":  

    s = "313551"
    largestPalindrome(s)  

# This code is contributed by Rituraj Jain

C

// C# program to print the largest  
// palindromic number by permuting 
// digits of a number  
using System; 
using System.Collections.Generic;  

class GFG{ 

// Function to check if a number can be 
// permuted to form a palindrome number 
static bool possibility(Dictionary<int, int> m, 
                        int length, string s) 
{ 

    // Counts the occurrence of number 
    // which is odd 
    int countodd = 0; 

    for(int i = 0; i < length; i++) 
    { 

        // If occurrence is odd 
        if ((m[s[i] - '0'] & 1) != 0) 
            countodd++; 

        // If number exceeds 1 
        if (countodd > 1) 
            return false; 
    } 
    return true; 
} 

// Function to print the largest palindromic 
// number by permuting digits of a number 
static void largestPalindrome(string s) 
{ 

    // string length 
    int l = s.Length; 

    // Map that marks the occurrence of a number 
    Dictionary<int,  
               int> m = new Dictionary<int, 
                                       int>(); 

    for(int i = 0; i < 10; i++) 
        m[i] = 0; 

    for(int i = 0; i < l; i++) 
        m[s[i] - '0']++; 

    // Check the possibility of a 
    // palindromic number 
    if (possibility(m, l, s) == false) 
    { 
        Console.Write("Palindrome cannot be formed"); 
        return; 
    } 

    // string array that stores the largest 
    // permuted palindromic number 
    char []largest = new char[l]; 

    // Pointer of front 
    int front = 0; 

    // Greedily start from 9 to 0 and place the 
    // greater number in front and odd in the 
    // middle 
    for(int i = 9; i >= 0; i--) 
    { 

        // If the occurrence of number is odd 
        if ((m[i] & 1) != 0)  
        { 

            // Place one odd occurring number 
            // in the middle 
            largest[l / 2] = (char)(i + '0'); 

            // Decrease the count 
            m[i]--; 

            // Place the rest of numbers greedily 
            while (m[i] > 0) 
            { 
                largest[front] = (char)(i + '0'); 
                largest[l - front - 1] = (char)(i + '0'); 
                m[i] -= 2; 
                front++; 
            } 
        } 
        else 
        { 

            // If all numbers occur even times, 
            // then place greedily 
            while (m[i] > 0) 
            { 

                // Place greedily at front 
                largest[front] = (char)(i + '0'); 
                largest[l - front - 1] = (char)(i + '0'); 

                // 2 numbers are placed, so  
                // decrease the count 
                m[i] -= 2; 

                // Increase placing position 
                front++; 
            } 
        } 
    } 

    // Print the largest string thus formed 
    for(int i = 0; i < l; i++) 
    { 
        Console.Write(largest[i]); 
    } 
} 

// Driver Code 
public static void Main(string[] args) 
{ 
    string s = "313551"; 

    largestPalindrome(s); 
} 
} 

// This code is contributed by rutvik_56

输出：

时间复杂度：O(n)，其中n是字符串的长度。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/36232.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-31》

分类

最近更新

dsal 通过排列数字得到的最大回文数

通过排列数字得到的最大回文数

C++

Python3

C

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-31》

dsal 通过排列数字得到的最大回文数

通过排列数字得到的最大回文数

C++

Python3

C

留言

联系客服

dsal 查看更多书籍