Джава. Как объединить две изначально отсортированные очереди в одну очередь? (без связанных списков или чего-то еще)
Например, у меня есть первая очередь: передняя [1 3 5 7] задняя и вторая очередь передняя [2 4 6 8] задняя. Новая объединенная очередь должна быть: front[1 2 3 4 5 6 7 8]back. Или первая очередь: спереди [1 3 3 7] сзади, вторая: спереди [2 4 5 7 8] сзади. Новая объединенная очередь: передняя [1 2 3 3 4 5 7 7 8] задняя. И мы не можем использовать любые виды сортировки. Вот моя реализация очереди:
public class QueueImpl implements IntQueue {
protected int capacity;
public static final int CAPACITY = 100;
protected int Q[];
protected int f = 0, r = 0;
public QueueImpl() {
this(CAPACITY);
}
public QueueImpl(int cap) {
capacity = cap;
Q = new int[capacity];
}
public void enqueue(int value) throws Exception {
if (getSize() == capacity - 1) {
throw new Exception("Full"); //To change body of generated methods, choose Tools | Templates.
}
Q[r] = value;
r = (r + 1) % capacity;
}
public int dequeue() throws Exception {
int element;
if (isEmpty()) {
throw new Exception("Empty"); //To change body of generated methods, choose Tools | Templates.
}
element = Q[f];
f = (f + 1) % capacity;
return element;
}
public int getSize() {
return (capacity - f + r) % capacity;
}
public boolean isEmpty() {
return (f == r);
}
public String toString() {
int z = f;
String s;
s = "f[";
if (getSize() >= 1) {
s += Q[0];
for (int i = 1; i <= getSize() - 1; i++) {
s += " " + Q[z + 1];
z = (z + 1) % capacity;
}
}
return s + "]b";
}
}
Мое решение: открытый класс Assign2Problem3Solution {
public static IntQueue merge(IntQueue q1, IntQueue q2) throws Exception {
IntQueue merged = new QueueImpl();
int a, b, k, t, m;
if (a < b) {
k = a;
t = b - a;
} else {
k = b;
t = a - b;
}
for (int i = 0; i < k; i++) {
a = q1.dequeue();
b = q2.dequeue();
if (a < b) {
merged.enqueue(a);
merged.enqueue(b);
} else if (b < a) {
merged.enqueue(b);
merged.enqueue(a);
}
}
if (q1.getSize() > q2.getSize()) {
for (int i = 0; i < t; i++) {
m = q1.dequeue();
merged.enqueue(m);
}
} else if (q1.getSize() < q2.getSize()) {
for (int i = 0; i < t; i++) {
m = q2.dequeue();
merged.enqueue(m);
}
}
return merged;
}
}
Вот код, который работает и удовлетворяет условиям:
IntQueue merged = new QueueImpl (); int a, b;
if (!q1.isEmpty() && !q2.isEmpty()) {
a = q1.dequeue();
b = q2.dequeue();
while (true) {
if (a < b) {
merged.enqueue(a);
if (q1.isEmpty()) {
merged.enqueue(b);
break;
}
a = q1.dequeue();
} else {
merged.enqueue(b);
if (q2.isEmpty()) {
merged.enqueue(a);
break;
}
b = q2.dequeue();
}
}
}
if (q1.getSize() > 0) {
while (!q1.isEmpty()) {
a = q1.dequeue();
merged.enqueue(a);
}
} else if (q2.getSize() > 0) {
while (!q2.isEmpty()) {
b = q2.dequeue();
merged.enqueue(b);
}
}
return merged;
3 ответа
Проблема здесь:
a = q1.dequeue();
b = q2.dequeue();
if (a < b) {
merged.enqueue(a);
merged.enqueue(b);
} else if (b < a) {
merged.enqueue(b);
merged.enqueue(a);
}
Этот код означает удаление одного элемента из первой очереди и удаление одного элемента из второй очереди. Добавьте меньший элемент в объединенную очередь, а затем добавьте больший элемент в объединенную очередь.
Приведенный выше код не работает в некоторых случаях. Одним из примеров является это. Рассмотрим две очереди Q1 = {1, 2, 3} и Q2 = {4, 5, 6}. На шаге 1 (цикл, k = 0) мы удаляем 1 из Q1 и 4 из Q2. Поскольку 1 меньше 4, мы добавляем 1, а затем 4. Объединенная очередь: {1, 4}, Q1 теперь {2, 3}, а Q2 теперь {5, 6}. На шаге 2 (цикл, k = 1) мы удаляем 2 из Q1 и 5 из Q2. Поскольку 2 меньше 5, мы добавляем 2, а затем 5. Объединенная очередь теперь {1, 4, 2, 5}. Обратите внимание, что хотя 2 меньше 4, мы добавляем 2 после 4, что неверно. Проблема здесь в том, что на шаге 1 мы не можем сразу добавить 4, потому что следующий элемент в Q1 (который равен 2) может быть меньше 4.
Что вам нужно сделать, это что-то вроде этого:
int e1 = q1.dequeue();
int e2 = q2.dequeue();
while (true) {
if (e1 < e2) {
merged.enqueue(e1);
if (q1.isEmpty()) {
// add remaining q2 elements
while (!q2.isEmpty()) {
merged.enqueue(q2.dequeue());
}
break;
}
// take another element from q1
e1 = q1.dequeue();
} else {
merged.enqueue(e2);
if (q2.isEmpty()) {
// add remaining q1 elements
while (!q1.isEmpty()) {
merged.enqueue(q1.dequeue());
}
break;
}
// take another element from q2
e2 = q2.dequeue();
}
}
Если у вас есть метод, который может извлечь элемент head, не удаляя его из очереди, код может быть намного чище.
Реализуйте метод peek() и сравнивайте значения по мере их просмотра, чтобы увидеть, какой из них меньше, и начните добавлять их в новую очередь.
В значительной степени часть слияния "MergeSort"
Вы можете просто сделать следующее:
C = new queue
a = A.poll()
b = B.poll()
While A or B is NOT EMPTY
while( b < a )
- C.put(b)
- b = B.Poll()
- C.put(a)
- a = A.poll()
FILL C with the queue left
Это просто чередование обоих списков, каждый раз принимая число, ближайшее к последнему числу в C. В конце вы просто заполняете последнее число из очереди, которая не является пустой.
Вы должны обратить внимание на пустой список, здесь это просто очень простой псевдокод, но когда я делаю "b = B.Poll()", я должен обратить внимание, есть ли еще элемент в B или нет, иначе это может бросить исключение.
Ну, я только что попробовал это на простом примере, я не говорю, что он работает на 100%, но он дает вам идеи. Ps: здесь мой "опрос" => "dequeue" для вашего класса