leetcode
leetcode 1851 ~ 1900
序列顺序查询

序列顺序查询

难度:

标签:

题目描述

代码结果

运行时间: 473 ms, 内存: 38.7 MB


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

// Class to represent a point of interest with a name and score
class Point {
    String name;
    int score;

    public Point(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

// Main class to handle the addition of points and retrieval of the i-th best point using streams
public class SORTracker {
    private List<Point> points;
    private int queryCount;

    public SORTracker() {
        points = new ArrayList<>();
        queryCount = 0;
    }

    // Adds a new point with a name and score to the tracker
    public void add(String name, int score) {
        Point newPoint = new Point(name, score);
        points.add(newPoint);
    }

    // Retrieves the i-th best point (where i is the current query count) using streams
    public String get() {
        queryCount++;
        return points.stream()
            .sorted(Comparator.comparing(Point::getScore).reversed().thenComparing(Point::getName))
            .map(Point::getName)
            .collect(Collectors.toList())
            .get(queryCount - 1);
    }
}

解释

方法:

此题解利用了sortedcontainers库中的SortedList数据结构,以维持景点的有序状态。每个景点以元组(-score, name)的形式存储,这样可以确保景点在列表中自动按照评分降序和字典序升序排列。添加操作直接将景点元组插入SortedList,由于SortedList内部机制,插入后列表仍然保持有序。查询操作则根据累积的查询次数n(self.n),从SortedList中获取第n好的景点。

时间复杂度:

add: O(log n), get: O(1)

空间复杂度:

O(n)

代码细节讲解

🦆
SortedList数据结构在插入和查询操作中的时间复杂度是多少?
SortedList数据结构通过维护一个内部平衡二叉搜索树(通常是红黑树或AVL树)来实现其功能。因此,在SortedList中插入一个元素的时间复杂度为O(log n),其中n是列表中的元素数量。查询(包括按索引访问)操作的时间复杂度也是O(log n)。这使得SortedList在处理需要频繁插入和随机访问的场景下非常高效。
🦆
SortedList是如何确保在元组(-score, name)中,评分相同的情况下能自动按字典序排序?
SortedList在进行元素比较时会依次比较元组中的每个元素。在这个问题的上下文中,元组的第一个元素是-score(评分的相反数),这样评分高的元素会被视为较小(因为负数越小其原始评分越高)。当两个景点的-score相等时,SortedList会比较元组的第二个元素,即景点的名字。因为字符串比较是按字典序进行的,所以这自然地实现了在评分相同的情况下按字典序对景点名进行排序。
🦆
为什么要选择使用SortedList而不是其他数据结构如优先队列或平衡二叉搜索树?
SortedList被选择用于这个应用主要因为它同时支持高效的插入和精确索引访问。优先队列(通常实现为二叉堆)虽然可以高效地支持插入和获取最小(或最大)元素,但它不支持O(log n)时间复杂度的随机位置访问。平衡二叉搜索树虽然能提供这两种操作的高效支持,但直接使用现成的SortedList库可以简化实现并减少出错的可能性。SortedList内部可能就是使用类似平衡二叉搜索树的结构实现的,它提供了现成的、经过优化的方法用于管理按顺序排列的元素,这些方法正好符合题目的需求。

相关问题