降低给定任务的时间复杂度

Question

我有一个商品，它有名称和价格。

现在我的程序输入包含一些命令列表，这些命令指示我可以添加新项或以以下格式选择项:

添加，item-name, item-price ->将带有price的item-name添加到我的列表中。Select，，——>选择在索引k处价格最低的商品名称，并打印到输出。如果多个商品价格相同，则按升序选择名称。

示例1:

输入:

Add, Apple, 4
Add, Ball, 3
Select, , 
Add, Toy, 5
Add, Pen, 1
Select, , 

输出:

Ball, Ball

解释:

首先我们添加Apple和Ball。所以按价格排序的物品[Ball(3)， Apple(4)]。初始化k为0。然后出现"选择"。得到索引k=0处的item，也就是Ball。现在，当选择发生时，将k增加到1。然后我们加上玩具和钢笔。所以按价格排序的物品[钢笔(1)，球(3)，苹果(4)，玩具(5)]。现在k等于1。然后出现"选择"。得到索引k=1处的item也就是Ball。现在，当选择发生时，将k增加到2。

So output is Ball, Ball.

示例2:

输入:

Add, Apple, 4
Add, Ball, 3
Select, , 
Select, , 
Add, Toy, 5
Select, , 

输出:

Ball, Apple, Toy

解释:

首先我们添加Apple和Ball。所以按价格排序的物品[Ball(3)， Apple(4)]。初始化k为0。然后出现"选择"。得到索引k=0处的item，也就是Ball。现在，当选择发生时，将k增加到1。然后出现"选择"。get item at index k=1，也就是苹果。现在，当选择发生时，将k增加到2。然后我们加上Toy。所以按价格排序的物品[球(3)，苹果(4)，玩具(5)]。现在k等于2。然后出现"选择"。得到索引k=2处的item，也就是Toy。现在，当选择发生时，将k增加到3。

So output is Ball, Apple, Toy.

这是我试过的代码:

public static void main(String[] args) {
System.out.println(process(Arrays.asList(Arrays.asList("Add", "Apple", "4"), Arrays.asList("Add", "Ball", "3"),
Arrays.asList("Select", "", ""), Arrays.asList("Add", "Toy", "5"), Arrays.asList("Add", "Pen", "1"),
Arrays.asList("Select", "", ""))));
System.out.println(process(Arrays.asList(Arrays.asList("Add", "Apple", "4"), Arrays.asList("Add", "Ball", "3"),
Arrays.asList("Select", "", ""), Arrays.asList("Select", "", ""), Arrays.asList("Add", "Toy", "5"),
Arrays.asList("Select", "", ""))));
}
public static List<String> process(List<List<String>> input) {
List<String> list = new ArrayList<>();
PriorityQueue<Item> pq = new PriorityQueue<>();
int k = 0;
for (List<String> e : input) {
if ("Add".equals(e.get(0))) {
Item a = new Item(e.get(1), e.get(2));
pq.add(a);
} else {
List<Item> sorted = new ArrayList<>();
for (int i = 0; i <= k; i++) {
sorted.add(pq.poll());
}
Item itemAtK = sorted.get(sorted.size() - 1);
list.add(itemAtK.name);
pq.addAll(sorted);
k++;
}
}
return list;
}
}
class Item implements Comparable<Item> {
int price;
String name;
public Item(String name, String p) {
this.name = name;
this.price = Integer.parseInt(p);
}
public int compareTo(Item item) {
int c = price - item.price;
if (c == 0)
c = name.compareTo(item.name);
return c;
}

这里的时间复杂度是n^2*log(n)

如何减少这段代码的时间复杂度

基于stef注释修改的代码:

public static List<String> process(List<List<String>> input) {
List<String> list = new ArrayList<>();
PriorityQueue<Item> pq = new PriorityQueue<>();
for (List<String> e : input) {
if ("Add".equals(e.get(0))) {
Item a = new Item(e.get(1), e.get(2));
pq.add(a);
} else {
Item itemAtK = pq.poll();
list.add(itemAtK.name);
}
}
return list;
}

输入:

Add, Apple, 4
Add, Ball, 3
Select, , 
Add, Toy, 5
Add, Pen, 1
Select, , 

预期输出:

Ball, Ball

程序输出错误:

Ball, Pen

Answer 1

正如有人评论的那样，也许你需要的不是PriorityQueue。

下面是一个不平衡BST的实现:

public static List<String> process(List<List<String>> input) {
List<String> list = new ArrayList<>();
Item root = null;
int k = 0;
for (List<String> e : input) {
if ("Add".equals(e.get(0))) {
Item a = new Item(e.get(1), e.get(2));
root = Item.insert(root, a);
} else {
Item first = Item.itemAt(root, k);
list.add(first.name);
++k;
}
}
return list;
}

class Item implements Comparable<Item> {
int count;
private Item left;
private Item right;
int price;
String name;
public Item(String name, String p) {
this.name = name;
this.price = Integer.parseInt(p);
}
@Override
public int compareTo(Item item) {
int c = price - item.price;
if (c == 0)
c = name.compareTo(item.name);
return c;
}
public static Item insert(Item root, Item item) {
if (root == null) {
item.count = 1;
return item;
}
int c = item.compareTo(root);
if (c < 0) {
root.left = insert(root.left, item);
} else {
root.right = insert(root.right, item);
}
++root.count;
return root;
}
public static Item itemAt(Item root, int ix) {
if (root == null) {
return null;
}
if (root.left != null) {
if (ix < root.left.count) {
return itemAt(root.left, ix);
}
ix -= root.left.count;
}
if (ix == 0) {
return root;
}
--ix;
if (root.right != null) {
if (ix < root.right.count) {
return itemAt(root.right, ix);
}
}
return null;
}
}

平均复杂度为O(log(n))，但由于树是不平衡的，因此存在退化情况(当条目进入排序时)。

勘误表:O (n * log (n))