Find next bigger/smaller number

本文最后更新于：2024年10月25日 下午

题目背景

给定一个数，组成数字可任意排列组合，找出比这个数大一点或小一点的数。例如：给定231。大一点的数是312，小一点的数是132

原题重现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Suppose we have a 10 digit number 2139548760 stored in a list like this
[ 2, 1, 3, 9, 5, 4, 8, 7, 6, 0 ]

we can rearrange the digits to get the next highest number using those digits. This would give us
this
[ 2, 1, 3, 9, 5, 6, 0, 4, 7, 8 ]

We could also rearrange the digits to get the next lowest number using those digits. This would
give us this
[ 2, 1, 3, 9, 5, 4, 8, 7, 0, 6 ]

Write a program that reads in a 10 digit number and store the digits in a list.

Then the program asks the user to choose whether they want the next highest number or the next
lowest number.

The user chooses which one they want and the program rearranges the list to produce what they
want.

Finally the program prints out the 10 digit number that the user wanted.

#实现思路：（待补充）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
def swap(lst, index1, index2):
                               # function to swap elements at given indices in a list
    temp = lst[index1]
    lst[index1] = lst[index2]
    lst[index2] = temp



def selection_sort(given_list, length, start_index):
                               # function to perform selection sort on a sublist of given_list starting from start_index
    i = start_index
    while i != length:
        j = i
        min_index = i
        while j != length :
            if given_list[j] < given_list[min_index]:
                min_index = j
            j = j + 1
        swap(given_list, i, min_index)
        i = i + 1
    return given_list



def get_list(n):
                                  # function to convert an integer into a list of its digits
    i = 9
    lst=[0] * 10
    while i != -1:
        lst[i] = int(n % 10)
        n = n // 10
        i = i - 1
    return lst



def highest_digits(lst):
                                     # function to find the next highest number
    i = 9
    while i != 0 and (lst[i-1]) >= (lst[i]):
        i  = i - 1
                                     # i is the index of the digit that begin to sort
    if i == 0:
        return None
    else:
        start = i - 1
        j = 9
        while j > i and lst[j] <= lst[i-1]:
            j = j - 1
                                # j is the index of the digit that will replace the digit at index i-1
        swap(lst, start, j)
       # performing selection sort on the sublist starting from index i to get the next highest number
        selection_sort(lst, 10, i)
        return lst



def lowest_digits(lst):
                                                 # function to find the next lowest number
    i = 9
    while i != 0 and lst[i-1] <= lst[i]:
        i  = i - 1
                                                 # i is the index of the digit that begin to sort
    if i == 0:
        return None
    start = i - 1
    j = 9
    while j > i and lst[j] >= lst[i - 1]:
        j = j - 1
                                                # j is the index of the digit that will replace the digit at index i-1
    swap(lst, start, j)
                        # performing selection sort on the sublist starting from index i to get the next lowest number
    selection_sort(lst, 10, i)
    return lst



def get_input_digit():
    n = input("Please input a 10 digit number (not need space):")
    while len(n) != 10:
        n = input("Invalid input, please input a 10 digit number:")
    return int(n)


def get_input_key():
    key = input(
        "Choose whether they want the next highest number or the next lowest number. "
        "IF highest then input h IF lowest then input l:")
    while key not in ['h', 'H', 'l', 'L']:
        key = input(
            "Invalid input. Choose whether you want the next highest number or the next lowest number. "
            "If highest then input h, if lowest then input l:")
    return key


def print_result(next_num):
    i = 0
    while i != 10:
        print(next_num[i], end="")
        i = i + 1


# main program
def find_next_number():
    n = get_input_digit()
    key = get_input_key()
    lst = get_list(n)
    if key == "h" or key == "H":
                                          # finding the next highest number
        next_num = highest_digits(lst)
        if next_num is None:
            print("There is no higher number.")
        else:
            print_result(next_num)
    elif key == "l" or key == "L":
                                           # finding the next lowest number
        next_num = lowest_digits(lst)
        if next_num is None:
            print("There is no lower numver.")
        else:
            print_result(next_num)
find_next_number()