Ну, правда, вам не нужно динамическое программирование c для этого вопроса. Ни один случай на самом деле не основан на предыдущих случаях.
Поэтому вы можете написать эту функцию:
public static List<Integer> kthPersonNew(int k, List<Integer> p, List<Integer> q) {
List<Integer> res = new ArrayList<>();
for (int limit : q) {
int count = 0;
boolean added = false;
// For each person index
for (int i = 0; i < p.size(); i++) {
// If this person is higher than the needed limit - count it
if (p.get(i) >= limit) {
count++;
// If you have counted k persons than add the kth person to res and break
if (count == k) {
res.add(i + 1);
added = true;
break;
}
}
}
// In case no one was added than add 0
if (!added) {
res.add(0);
}
}
return res;
}
И он выдает тот же вывод для предоставленного вами теста.
p = [1, 4, 4, 3, 1, 2, 6]
q = [1, 2, 3, 4, 5, 6, 7]
=>
res = [2, 3, 3, 3, 0, 0, 0]
Теперь я уверен, что эта программа не вызовет java.lang.OutOfMemoryError, так как вы используете только один массив и он имеет одинаковую длину как q.
Это должно решить вашу проблему.
Редактировать:
Похоже, что новый алгоритм хорош для памяти, но недостаточно быстр, предполагая, что q мы всегда можем это использовать и убедиться, что временная сложность всегда меньше, чем O(q * k + n). Поскольку каждый элемент, который не соответствует текущему пределу, не будет соответствовать будущим пределам.
Нам понадобится вспомогательный класс:
class Element{
private int index;
private int value;
public Element(int index, int value){
this.index = index;
this.value = value;
}
public int getIndex(){
return this.index;
}
public int getValue(){
return this.value;
}
@Override
public String toString(){
return value + " " + index;
}
public void print(){
System.out.println(this);
}
}
, чтобы мы могли помните старый индекс переменных даже после удаления.
и новую функцию:
public static List<Integer> kthPersonFast(int k, List<Integer> p, List<Integer> q) {
List<Integer> res = new ArrayList<>();
List<Element> elements = new LinkedList<Element>();
for (int i = 0; i < p.size(); i++) {
elements.add(new Element(i, p.get(i)));
}
for (int limit : q) {
int count = 0;
boolean added = false;
// For each person
Iterator<Element> itr = elements.iterator();
while (itr.hasNext()) {
Element person = itr.next();
// If this person is higher than the needed limit - count it
if (person.getValue() >= limit) {
count++;
// If you have counted k persons than add the kth person to res and break
if (count == k) {
res.add(person.getIndex() + 1);
added = true;
break;
}
} else {
// If the person didn't fit for that limit it will not fit to any other limit
// since we are assuming the limits are always growing
itr.remove();
}
}
// In case no one was added than add 0
if (!added) {
res.add(0);
}
}
return res;
}
Вам также нужно будет импортировать:
import java.util.Iterator;
import java.util.LinkedList;
Это должно быть .
Удачи