华为OD机考算法题：磁盘容量排序

华为OD机考算法题：磁盘容量排序"/>

华为OD机考算法题：磁盘容量排序

题目部分

解读与分析

题目解读：

输入一组的表示容量的字符串，将每个字符串转换成相同单位大小的数字，进行比较，然后按照从小到大的顺序排序（稳定排序），输出。

分析与思路：

此题的关键问题在于解析字符串，然后把解析后的字符串转换成统一的单位 M ，之后对数据进行排序。

解析字符串需要遍历 1 次，排序的时间复杂度为 O(nlogn)，因此此算法的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

此题的思路与《华为OD机考算法题：日志排序》完全一致。

更进一步，可以把“解析后的字符串转换成统一的单位 M ”这个操作放到初始解析之后，排序之前，以免在排序过程中，每两两比较时都要进行转换，实际上对性能有影响。

代码实现

Java代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;/*** 磁盘容量排序* * @since 2023.11.02* @version 0.1* @author Frank**/
public class DiskCapacity {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();int count = Integer.parseInt(input);String[] numArr = new String[count];for (int i = 0; i < count; i++) {input = sc.nextLine();numArr[i] = input;}processDiskCapacity(numArr);}}private static void processDiskCapacity(String[] numArr) {Comparator<String> comp = new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {int o1Capacity = parseCapacity(o1);int o2Capacity = parseCapacity(o2);return o1Capacity - o2Capacity;}};Arrays.sort(numArr, comp);for (int i = 0; i < numArr.length; i++) {System.out.println(numArr[i]);}}private static int parseCapacity(String input) {int ret = 0;int start = 0;int i = 0;while( i < input.length() ){char curChar =  input.charAt( i );while( curChar >= '0' && curChar <= '9' ){i ++;curChar =  input.charAt( i );}String intStr = input.substring( start, i );int curValue = Integer.parseInt( intStr );int times = 1;if( curChar == 'M' ){times = 1;}else if( curChar == 'G' ){times = 1024;}else if( curChar == 'T' ){times = 1024 * 1024;}curValue = curValue * times;ret += curValue;i ++;start = i;}return ret;}}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var count = parseInt(line);var numArr = new Array();for (var i = 0; i < count; i++) {line = await readline();numArr[i] = line;}processDiskCapacity(numArr);}
}();function processDiskCapacity(numArr) {var comp = function(o1, o2) {var o1Capacity = parseCapacity(o1);var o2Capacity = parseCapacity(o2);return o1Capacity - o2Capacity;};numArr.sort(comp);for (var i = 0; i < numArr.length; i++) {console.log(numArr[i]);}
}function parseCapacity(input) {var ret = 0;var start = 0;var i = 0;while (i < input.length) {var curChar = input.charAt(i);while (curChar >= '0' && curChar <= '9') {i++;curChar = input.charAt(i);}var intStr = input.substring(start, i);var curValue = parseInt(intStr);var times = 1;if (curChar == 'M') {times = 1;} else if (curChar == 'G') {times = 1024;} else if (curChar == 'T') {times = 1024 * 1024;}curValue = curValue * times;ret += curValue;i++;start = i;}return ret;
}

(完)