整型数组按个位值排序 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

给定一个非空数组(列表)，其元素数据类型为整型，请按照数组元素十进制最低位从小到大进行排序，十进制最低位相同的元素，相对位置保持不变
当数组元素为负值时，十进制最低位等同于去除符号位后对应十进制值最低位。

输入描述

给定一个非空数组，其元素数据类型为32位有符号整数，数组长度[1,1000]

输出描述

输出排序后的数组

示例1

输入：
1,2,5,-21,22,11,55,-101,42,8,7,32

输出：
1,-21,11,-101,2,22,42,32,5,55,7,8

题解

这道题目是关于排序算法的问题，具体来说是按照数组元素的十进制最低位及元素索引位置进行排序。、

解题思路

首先，读入非空数组，将数组中的每个元素按照题目要求计算其十进制最低位，并记录下来该元素的索引位置和原始值。

创建一个辅助数组或列表，将每个元素的十进制最低位、索引位置和原始值组成一个元组，放入辅助数组中。

使用排序算法对辅助数组进行排序，排序规则是按照十进制最低位从小到大排序，如果最低位相同，则按照索引位置从小到大排序。

排序完成后，从辅助数组中提取原始值，即为排序后的结果。

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] nums = Arrays.stream(scanner.nextLine().split(","))
                .mapToInt(Integer::parseInt).toArray();

        ArrayList<int[]> arr = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int t = nums[i];
            int d = (t < 0) ? (-t) % 10 : t % 10;
            arr.add(new int[]{d, i, t});
        }

        // 按照数组元素十进制最低位从小到大进行排序，十进制最低位相同的元素，相对位置保持不变(坐标升序)
        Collections.sort(arr, (a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            } else {
                return Integer.compare(a[0], b[0]);
            }
        });

        for (int i = 0; i < arr.size(); i++) {
            System.out.print(arr.get(i)[2]);
            if (i + 1 == arr.size())
                System.out.println();
            else
                System.out.print(',');
        }
    }
}

Python

def main():
    nums = list(map(int, input().split(",")))

    arr = []
    for idx, t in enumerate(nums):
        d = (-t) % 10 if t < 0 else t % 10  # 最低位元素值
        arr.append((d, idx, t))

    arr.sort()
    rs = list(map(lambda x: x[2], arr))
    print(*rs, sep=',')


if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // 元素值 vector<int> {最低位元素值, 元素在原数组中的索引位置， 数组中元素值}
    vector<vector<int>> arr;

    int t, idx = 0;
    while (cin >> t) {
        int d = (t < 0) ? (-t) % 10 : t % 10;   // 最低位元素值
        arr.push_back({d, idx, t});

        if (cin.peek() == ',') cin.ignore();
        idx++;
    }

    sort(arr.begin(), arr.end());
    for (size_t i = 0; i < arr.size(); i++) {
        cout << arr[i][2];
        if (i + 1 == arr.size())
            cout << endl;
        else
            cout << ',';
    }
    return 0;
}