【华为OD题库-088】数字最低位排序-Java

2023-12-12 23:29

本文主要是介绍【华为OD题库-088】数字最低位排序-Java,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

给定一个非空数组(列表),元素数据类型为整型
请按照数组元素十进制最低位从小到大进行排序
十进制最低位相同的元素,相对位置保持不变
当数组元素为负值时,十进制最低位等同于去除符号位后对应十进制值最低位
输入描述
给定一个非空数组(列表)
其元素数据类型为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

思路

简单排序题,因为要求相对位置不变,所以需要稳定的排序算法,
常见的稳定排序有:冒泡排序,插入排序,归并排序
不稳定的排序有:选择排序,快速排序
本文作为对排序的回顾,写了上述所有的排序算法代码

题解

package hwod;import java.util.Arrays;
import java.util.Scanner;public class NumSortLowest {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();int[] res = mergeSort(nums);for (int i = 0; i < res.length; i++) {if (i != 0) System.out.print(",");System.out.print(res[i]);}}// 冒泡排序,稳定,可取private static int[] bubblingSort(int[] nums) {for (int i = 0; i < nums.length - 1; i++) {int flag = 0;for (int j = 0; j < nums.length - 1 - i; j++) {if (Math.abs(nums[j]) % 10 > Math.abs(nums[j + 1]) % 10) {swap(nums, j, j + 1);flag = 1;}}if (flag == 0) break;}return nums;}// 插入排序,稳定可取private static int[] insertSort(int[] nums) {for (int i = 1; i < nums.length; i++) {int key = nums[i];int j = i - 1;while (j >= 0 && Math.abs(nums[j]) % 10 > Math.abs(key) % 10) {nums[j + 1] = nums[j];j--;}nums[j + 1] = key;}return nums;}//归并排序,稳定可取private static int[] mergeSort(int[] nums) {recur2(nums, 0, nums.length - 1);return nums;}private static void recur2(int[] nums, int start, int end) {if (start >= end) return;int mid = start + end >> 1;recur2(nums, start, mid);recur2(nums, mid + 1, end);int i = start, j = mid + 1, k = 0;int[] tmp = new int[end - start + 1];while (i <= mid || j <= end) {if (j > end || (i <= mid && Math.abs(nums[i]) % 10 <= Math.abs(nums[j]) % 10)) {tmp[k++] = nums[i++];} else {tmp[k++] = nums[j++];}}for (int m = 0; m < tmp.length; m++) {nums[start + m] = tmp[m];}}//选择排序,不稳定,本题不可取private static int[] selectSort(int[] nums) {for (int i = 0; i < nums.length - 1; i++) {int minIdx = i;for (int j = i + 1; j < nums.length; j++) {if (Math.abs(nums[minIdx]) % 10 > Math.abs(nums[j]) % 10) {minIdx = j;}}if (minIdx != i) {swap(nums, i, minIdx);}}return nums;}// 快速排序,不稳定,本题不可取private static int[] quickSort(int[] nums) {recur(nums, 0, nums.length - 1);return nums;}private static void recur(int[] nums, int start, int end) {if (start >= end) return;int i = start, j = end, pivot = nums[i];while (i < j) {while (Math.abs(nums[j]) % 10 > Math.abs(pivot) % 10 && i < j) j--;while (Math.abs(nums[i]) % 10 <= Math.abs(pivot) % 10 && i < j) i++;if (i < j) {swap(nums, i, j);}}swap(nums, i, start);recur(nums, start, i - 1);recur(nums, i + 1, end);}private static void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}}

推荐

如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。

这篇关于【华为OD题库-088】数字最低位排序-Java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/486308

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技