华为OD机考算法题：支持优先级的队列

题目部分

解读与分析

题目解读：

输入一个字符串，把字符串解析成各种队列数据，根据优先级输出数据，如果优先级相同，则按照原顺序输出。

分析与思路：

分两步实现。
1. 解析：对收入的字符串以 “(” 和 “)” 配对，解析成每组数据元素 element，包括数据内容（element[0]）和数据优先级( element[1] )。并把它放到数组 dataArray （dataArray 的元素为 element）中。
2. 排序：对数组中的数据进行排序，排序的规则为按照每个元素的 element[1] 大小排序（从大到小）。
3. 输出：对排序的元素，逐个输出数据内容（element[0]），需要注意的是，如果前一个输出的数据的内容和优先级与当前即将输出的数据相等，则忽略，继续下一个。

此算法的时间复杂度和空间复杂度均为 O(n)。

代码实现

Java代码

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 支持优先级的队列
 * 
 * @since 2023.10.26
 * @version 0.1
 * @author Frank
 *
 */
public class PriorityQueue {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext()) {
	    String input = sc.nextLine();
	    int[][] elements = getElements( input );
	    sort( elements );
	    output( elements );
	}
    }

    private static int[][] getElements( String input )
    {
	List<int[]> eleList = new ArrayList();
	
	int indexLeft = 0;
	int indexRight = 0;
	
	while( indexLeft != -1)
	{
	    indexLeft = input.indexOf( "(",  indexRight );
	    indexRight = input.indexOf( ")",  indexRight );
	    if( indexLeft == -1 )
	    {
		break;
	    }
	    String eleStr = input.substring( indexLeft + 1, indexRight );
	    String[] eleArr = eleStr.split( "," );
	    int[] element = new int[2];
	    element[0] = Integer.parseInt( eleArr[0] );
	    element[1] = Integer.parseInt( eleArr[1] );
	    eleList.add( element );
	    
	    indexRight += 1;
	}
	
	int[][] ret = new int[eleList.size()][2];
	for( int i = 0; i < eleList.size(); i ++ )
	{
	    ret[i] = eleList.get( i );
	}
	
	return ret;
    }
    
    private static void sort( int[][] elements) {
	Arrays.sort( elements, new Comparator<int[]>() {
	    @Override
	    public int compare(int[] o1, int[] o2) {
		return o2[1] - o1[1];
	    }
	    
	} );
    }

    private static void output( int[][] elements ) {
	StringBuffer sb = new StringBuffer();
	for( int i = 0; i < elements.length; i ++ )
	{
	    if( i > 0 && ( elements[i][0] ==  elements[i - 1][0] ) && ( elements[i][1] ==  elements[i - 1][1] )  ) {
		continue;
	    }
	    sb.append( elements[i][0] + "," );
	}
	String ret = sb.toString();
	ret = ret.substring( 0, ret.length() - 1);
	System.out.println( 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 elements = getElements(line);
        sort(elements);
        output(elements);
    }
}();

function getElements(input) {
    var eleList = new Array();

    var indexLeft = 0;
    var indexRight = 0;

    while (indexLeft != -1) {
        indexLeft = input.indexOf("(", indexRight);
        indexRight = input.indexOf(")", indexRight);
        if (indexLeft == -1) {
            break;
        }
        var eleStr = input.substring(indexLeft + 1, indexRight);
        var eleArr = eleStr.split(",");
        var element = new Array();
        element[0] = parseInt(eleArr[0]);
        element[1] = parseInt(eleArr[1]);
        eleList.push(element);

        indexRight += 1;
    }

    return eleList;
}

function sort( elements ) {
    elements.sort( function( a, b) {
        return b[1] - a[1];
    })
}

function output( elements ) {
    var ret = "";
    for( var i = 0; i < elements.length; i ++ )
    {
        if( i > 0 && ( elements[i][0] ==  elements[i - 1][0] ) && ( elements[i][1] ==  elements[i - 1][1] )  ) {
        continue;
        }
        ret += ( elements[i][0] + "," );
    }
    ret = ret.substring( 0, ret.length - 1);
    console.log( ret );
}

(完)