Make writing a habit together! This is the 12th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

describe

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.
Copy the code

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.
Copy the code

Note:

1 <= num <= 10^9

parsing

If you are given a positive integer num, you can swap any two odd numbers or any two even numbers of num, swap them an infinite number of times, and return the maximum possible value of num.

Game look at the questions think this problem is very simple, and write their own code is a bit repetitive, always want to optimize the code, but gave up, because event, every brother are watching after talking about the code, is also long, only to find they and I write is a level, instant did not have the desire to optimize the code.

Sort an array by sorting an array by sorting an array by sorting an array

  • Change num to list NUMs because strings cannot be modified in index positions
  • Take all the even numbers in NUMs and put them in A, and then sort A in descending order
  • Place the elements in A, in descending order, back to the previous even positions in NUMs
  • Take all the odd numbers from NUMs and put them in B, and then sort B in descending order
  • Place the elements in B, in descending order, back to the previously odd positions in NUMs
  • Concatenate NUMS into a string

The time complexity is O(N + NlogN), and the space complexity is O(N).

answer

class Solution(object):
    def largestInteger(self, num):
        """
        :type num: int
        :rtype: int
        """
        nums = list(str(num))
        N = len(nums)
        A = [i for i in nums if int(i)%2 == 0]
        A.sort()
        A = A[::-1]
        n = 0
        for i in range(N):
            if int(nums[i])%2 == 0:
                nums[i] = A[n]
                n += 1
        B = [i for i in nums if int(i)%2 == 1]
        B.sort()
        B = B[::-1]
        n = 0
        for i in range(N):
            if int(nums[i])%2 == 1:
                nums[i] = B[n]
                n += 1
        return int(''.join(nums))		
Copy the code

The results

238/238 Test cases passed. Status: Accepted Runtime: 34 MS Memory Usage: 13.3 MBCopy the code

The original link

Leetcode.com/contest/wee…

Your support is my biggest motivation