如何应用比较器从按人口排序的列表中获取前 5 个城市？

Question

我有一个classCity

public final class City {
private final String name;
private final String state;
private final int    population;

public City(String name, String state, int population) {
    this.name       = name;
    this.state      = state;
    this.population = population;
}
public String getName() {
    return name;
}
public String getState() {
    return state;
}
public int getPopulation() {
    return population;
}
@Override
public String toString() {
    return "City [name=" + name + ", state=" + state + ", population=" + population + "]";
}
}

和实现 Observable 的 class（不需要）。这个 observable class 包含一个数组列表 List<City> cityList，其中包含已报告的所有 cities 的数据。

我的 class TopFiveCities 应该：

"implement a getter method getTopFive() returning a list with the five top cities (in terms of population) received. The list is sorted from higher to lower numbers. The returned list must be a copy of the list kept by the observer"

除了获得前 5 名之外，我还需要知道如何制作 copy list 来自 observer.

这是我的：

public class TopFiveCities
implements Observer {

// THIS ALSO DOESN'T WORK UNLESS THE LIST IS STATIC
// SO HOW CAN I MAKE A COPY OF THE LIST FROM OBSERVER?
private List<City> list = new ArrayList<>(CensusOffice.cityList);

public List<City> getTopFive() {
    Collections.sort(list, new Comparator<City>() {

        @Override
        public int compare(City o1, City o2) {
            return Integer.compare(o1.getPopulation(), o2.getPopulation());
        }
        
    });
    return list;
}

public void update(Observable observable) {
    if (!(observable instanceof Observable)) {
        throw new IllegalArgumentException();
    }
}
}

有了这个，当样本输出之一应该是：

City [name=Chicago, state=IL, population=2746388]

我刚收到所有个城市的列表，按人口从 LOWEST 到 HIGHEST.我做错了什么？

Answer 1

int order = requestedOrder.equals("asc") ? 1 : -1;

Collections.sort(list, new Comparator<CustomObj>() {
    public int compare(CustomObj first, CustomObj scnd) {
        return first.getComparableParam().compareTo(scnd.getComparableParam()) * order;
    }
});

我刚刚在评论中从推荐的 stackover 页面复制并传递了这个代码块。如果您想要升序，只需更改它即可。在您的代码中，订单将是 -1.

简单地说，你需要乘以-1。

return Integer.compare(o1.getPopulation(), o2.getPopulation()) * -1;

在此之后您可以将其子列表。

您将列表保留为全局变量，它可以通过更新方法访问，但如果 class 是单例，则它不会更改，但更新方法除外。您的更新方法可以通过通知

来改变它

在更新方法中，您可以通过 list.addAll

简单地清除和添加新列表

Answer 2

由于这是一项学校作业，我将描述这些部分，但让您 assemble 将它们变成最终代码。

I have a class "City"

您可以更简短地将 class 定义为 record。

City ( String name, String state, int population ) {}

holds an array list "List cityList"

List < City > cities = new ArrayList<>();

getting the top 5 list

Sort the list by 。您可以使用访问器“getter”方法的方法引用来创建用于排序的比较器。但请注意，默认情况下，记录不使用“get”一词作为访问者，它们只使用属性.

的名称

cities.sort( Comparator.comparing( City :: population ).reversed() ) ;

对于不可修改的列表，请调用 List.of 或 List.copyOf。

List#subset 为您提供了一个包含原始元素的列表。但要注意：结果列表是基于原始列表的视图。子集不是分开的和独立的。要获得单独的列表，请传递给 List.copyOf 或传递给另一个 List 实现的构造函数。

List< City > topFivePop = List.copyOf( subset ) ;

Answer 3

你可以只使用 Stream，使用 Comparator 对流进行排序，限制元素数量并将元素转换为新列表：

List<City> top5citiesByPopulation = cities.stream()
        .sorted(Comparator.comparing(City::getPopulation).reversed())
        .limit(5)
        .collect(Collectors.toList());

Answer 4

这个问题不需要对整个给定列表进行排序，其时间复杂度为 O(n log n).

基本上，该任务有点类似于查找列表中的最大元素，可以在 O(n) 时间内通过一次给定列表完成。

这个问题最合适的方法是部分排序，可以实现的最佳性能是O( n) 和 O(n log n).

为了在列表中找到5 最大元素，我们可以维护一个集合，它将存储在排序顺序 最多 5 以前遇到元素具有最大值。

比集合中的最小元素小的元素将被自动丢弃如果集合的大小已经 5。只有值高于 最小元素 值的新元素才会触发对这个小集合的重新排序。 IE。数据将被部分排序，而不是对整个数据集进行排序。

在下面的实现中，对于将存储 5 个最大元素的 collection，我选择了 PriorityQueue.

根据documentation，它的方法具有以下时间复杂度。

this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

即添加一个新元素和删除第一个元素都将以对数时间执行，并使用方法[=访问队列中的最小值18=] 在 O(1) 时间内完成（几乎立即）。

PriorityQueue 封装在通用 class 中，构造函数 期望作为参数 Comparator<T> 和所需的最大队列大小（ 即需要找到的最大元素数 ）。

队列本身不暴露给外部classes。方法 addItem() 处理给定的元素和 getFirstN returns 排序的不可变列表。

下面代码中的

Comparator是使用静态方法comparingInt()实现的。您还可以通过为其抽象方法 compare() 通过使用 lambda 表达式 或在 匿名内部 class.

public class FirstN<T> {
    private final Queue<T> queue;
    private final Comparator<T> comparator;
    private final int capacity;

    public FirstN(Comparator<T> comparator, int capacity) {
        this.queue = new PriorityQueue<>(comparator);
        this.comparator = comparator;
        this.capacity = capacity;
    }

    public boolean addItem(T item) {
        if (capacity == queue.size() && comparator.compare(item, queue.element()) <= 0) {
            return false; // queue is full and the given item is smaller than the lowerest element in the queue
        }

        if (capacity == queue.size() && comparator.compare(item, queue.element()) > 0) {
            queue.remove(); // removing the first element if it's smaller than the given item
        }
        return queue.add(item); // adding the given item
    }

    public List<T> getFirstN() {
        List<T> result = new ArrayList<>(queue); // creating a list based on a queue
        result.sort(comparator);
        return List.copyOf(result); // making a copy of the list (returned list is immutable)
    }
}

main()

public static void main(String[] args) {
    List<City> cities = List.of(
            new City("Austin", "Texas", 1028225),
            new City("Los Angeles", "California", 3985516),
            new City("San Diego", "California", 1429653),
            new City("Houston", "Texas", 2325353),
            new City("Phoenix", "Arizona", 1759943),
            new City("New York City", "New York", 8177025),
            new City("San Antonio", "Texas", 1598964),
            new City("Philadelphia", "Pennsylvania", 1585480),
            new City("San Diego", "California", 1429653),
            new City("Chicago", "Illinois", 2671635),
            new City("Dallas", "Texas", 1348886));

    FirstN<City> top5Cities =
            new FirstN<>(Comparator.comparingInt(City::getPopulation), 5);

    for (City next: cities) {
        top5Cities.addItem(next);
    }

    List<City> result = top5Cities.getFirstN(); // contains 5 biggest US cities

    result.forEach(System.out::println); // printing the result
}

输出（从低到高排序）

City [name=Phoenix, state=Arizona, population=1759943]
City [name=Houston, state=Texas, population=2325353]
City [name=Chicago, state=Illinois, population=2671635]
City [name=Los Angeles, state=California, population=3985516]
City [name=New York City, state=New York, population=8177025]

如何应用比较器从按人口排序的列表中获取前 5 个城市？

How to apply comparator to get the TOP 5 cities from a List sorted by population?

java

list

algorithm

comparator

observer-pattern