Oto rozwiązanie, które nie opiera się na złożonej matematyce, jak robią to odpowiedzi sdcvvc / Dimitris Andreou, nie zmienia tablicy wejściowej tak, jak zrobili to caf i pułkownik Panic, i nie używa zestawu bitów o ogromnych rozmiarach, jak Chris Lercher, JeremyP i wiele innych zrobiło. Zasadniczo zacząłem od pomysłu Svalorzen / Gilada Deutcha na drugi kwartał, uogólniłem go na wspólny przypadek Qk i zaimplementowałem w Javie, aby udowodnić, że algorytm działa.
Pomysł
Załóżmy, że mamy dowolny przedział I, o którym wiemy tylko, że zawiera on co najmniej jedną z brakujących liczb. Po jednym przejściu przez tablicę wejściowego, patrząc tylko na numerach od I , można otrzymać zarówno sumy S , a ilość Q brakujących numerów z I . Robimy to po prostu zmniejszając długość I za każdym razem, gdy napotykamy liczbę od I (dla uzyskania Q ) i zmniejszając z góry obliczoną sumę wszystkich liczb w I o tę napotkaną liczbę za każdym razem (dla uzyskania S ).
Teraz patrzymy na S i Q . Jeśli Q = 1 , oznacza to, że wówczas , że zawiera tylko jeden z brakujących numerów, a ta liczba jest wyraźnie S . Oznaczamy I jako ukończony (w programie nazywa się to „jednoznacznym”) i nie uwzględniamy go w dalszych rozważaniach. Z drugiej strony, gdy Q> 1 , można obliczyć średnią A = S / P brakujących numerów zawartych w I . Ponieważ wszystkie liczby są różne, co najmniej jeden z tych numerów jest mniejsze niż A i co najmniej jeden jest większy od A . Teraz podzieliliśmy I na A.na dwa mniejsze przedziały, z których każdy zawiera co najmniej jedną brakującą liczbę. Zauważ, że nie ma znaczenia, do których przedziałów przypisujemy A, jeśli jest to liczba całkowita.
Wykonujemy kolejny przebieg tablicowy, obliczając S i Q osobno dla każdego z przedziałów (ale w tym samym przebiegu), a następnie zaznaczamy przedziały dla Q = 1 i przedziały podziału dla Q> 1 . Kontynuujemy ten proces, dopóki nie pojawią się nowe „dwuznaczne” przedziały, tzn. Nie mamy nic do podzielenia, ponieważ każdy przedział zawiera dokładnie jedną brakującą liczbę (i zawsze znamy tę liczbę, ponieważ znamy S ). Zaczynamy od jedynego przedziału „całego zakresu” zawierającego wszystkie możliwe liczby (np. [1..N] w pytaniu).
Analiza złożoności czasu i przestrzeni
Całkowita liczba przejść p, które musimy wykonać, aż do zatrzymania procesu, nigdy nie jest większa niż liczba brakujących liczb k . Nierówność p <= k można udowodnić rygorystycznie. Z drugiej strony istnieje również empiryczna górna granica p <log 2 N + 3, która jest przydatna dla dużych wartości k . Musimy przeprowadzić wyszukiwanie binarne dla każdej liczby tablicy wejściowej, aby określić przedział, do którego ona należy. Dodaje to mnożnik log k do złożoności czasu.
W sumie złożoność czasu wynosi O (N ᛫ min (k, log N) ᛫ log k) . Zauważ, że w przypadku dużego k jest to znacznie lepsze niż w przypadku metody sdcvvc / Dimitris Andreou, czyli O (N ᛫ k) .
Do swojej pracy algorytm wymaga O (k) dodatkowej przestrzeni do przechowywania w większości k przedziałów, która jest znacznie lepsza niż O (N) w rozwiązaniach „zestawu bitów”.
Implementacja Java
Oto klasa Java, która implementuje powyższy algorytm. Zawsze zwraca posortowaną tablicę brakujących liczb. Poza tym nie wymaga liczenia brakujących liczb k, ponieważ oblicza go w pierwszym przejściu. Cały zakres liczb jest podany przez parametry minNumberi maxNumber(np. 1 i 100 dla pierwszego przykładu w pytaniu).
public class MissingNumbers {
private static class Interval {
boolean ambiguous = true;
final int begin;
int quantity;
long sum;
Interval(int begin, int end) { // begin inclusive, end exclusive
this.begin = begin;
quantity = end - begin;
sum = quantity * ((long)end - 1 + begin) / 2;
}
void exclude(int x) {
quantity--;
sum -= x;
}
}
public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
Interval full = new Interval(minNumber, ++maxNumber);
for (inputBag.startOver(); inputBag.hasNext();)
full.exclude(inputBag.next());
int missingCount = full.quantity;
if (missingCount == 0)
return new int[0];
Interval[] intervals = new Interval[missingCount];
intervals[0] = full;
int[] dividers = new int[missingCount];
dividers[0] = minNumber;
int intervalCount = 1;
while (true) {
int oldCount = intervalCount;
for (int i = 0; i < oldCount; i++) {
Interval itv = intervals[i];
if (itv.ambiguous)
if (itv.quantity == 1) // number inside itv uniquely identified
itv.ambiguous = false;
else
intervalCount++; // itv will be split into two intervals
}
if (oldCount == intervalCount)
break;
int newIndex = intervalCount - 1;
int end = maxNumber;
for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
// newIndex always >= oldIndex
Interval itv = intervals[oldIndex];
int begin = itv.begin;
if (itv.ambiguous) {
// split interval itv
// use floorDiv instead of / because input numbers can be negative
int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
intervals[newIndex--] = new Interval(mean, end);
intervals[newIndex--] = new Interval(begin, mean);
} else
intervals[newIndex--] = itv;
end = begin;
}
for (int i = 0; i < intervalCount; i++)
dividers[i] = intervals[i].begin;
for (inputBag.startOver(); inputBag.hasNext();) {
int x = inputBag.next();
// find the interval to which x belongs
int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
if (i < 0)
i = -i - 2;
Interval itv = intervals[i];
if (itv.ambiguous)
itv.exclude(x);
}
}
assert intervalCount == missingCount;
for (int i = 0; i < intervalCount; i++)
dividers[i] = (int)intervals[i].sum;
return dividers;
}
}
Dla uczciwości klasa ta otrzymuje dane wejściowe w postaci NumberBagobiektów. NumberBagnie zezwala na modyfikację tablicy i losowy dostęp, a także liczy, ile razy tablica była wymagana do sekwencyjnego przechodzenia. Jest również bardziej odpowiedni do testowania dużych tablic niż Iterable<Integer>dlatego, że pozwala uniknąć intpakowania pierwotnych wartości i pozwala na zawijanie części dużego int[]dla wygodnego przygotowania testu. To nie jest trudne do zastąpienia, w razie potrzeby, NumberBagprzez int[]lub Iterable<Integer>wpisać findpodpis, zmieniając dwie pętle dla w nim na te foreach.
import java.util.*;
public abstract class NumberBag {
private int passCount;
public void startOver() {
passCount++;
}
public final int getPassCount() {
return passCount;
}
public abstract boolean hasNext();
public abstract int next();
// A lightweight version of Iterable<Integer> to avoid boxing of int
public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
return new NumberBag() {
int index = toIndex;
public void startOver() {
super.startOver();
index = fromIndex;
}
public boolean hasNext() {
return index < toIndex;
}
public int next() {
if (index >= toIndex)
throw new NoSuchElementException();
return base[index++];
}
};
}
public static NumberBag fromArray(int[] base) {
return fromArray(base, 0, base.length);
}
public static NumberBag fromIterable(Iterable<Integer> base) {
return new NumberBag() {
Iterator<Integer> it;
public void startOver() {
super.startOver();
it = base.iterator();
}
public boolean hasNext() {
return it.hasNext();
}
public int next() {
return it.next();
}
};
}
}
Testy
Proste przykłady demonstrujące użycie tych klas podano poniżej.
import java.util.*;
public class SimpleTest {
public static void main(String[] args) {
int[] input = { 7, 1, 4, 9, 6, 2 };
NumberBag bag = NumberBag.fromArray(input);
int[] output = MissingNumbers.find(1, 10, bag);
System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
Arrays.toString(input), Arrays.toString(output), bag.getPassCount());
List<Integer> inputList = new ArrayList<>();
for (int i = 0; i < 10; i++)
inputList.add(2 * i);
Collections.shuffle(inputList);
bag = NumberBag.fromIterable(inputList);
output = MissingNumbers.find(0, 19, bag);
System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
inputList, Arrays.toString(output), bag.getPassCount());
// Sieve of Eratosthenes
final int MAXN = 1_000;
List<Integer> nonPrimes = new ArrayList<>();
nonPrimes.add(1);
int[] primes;
int lastPrimeIndex = 0;
while (true) {
primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
int p = primes[lastPrimeIndex]; // guaranteed to be prime
int q = p;
for (int i = lastPrimeIndex++; i < primes.length; i++) {
q = primes[i]; // not necessarily prime
int pq = p * q;
if (pq > MAXN)
break;
nonPrimes.add(pq);
}
if (q == p)
break;
}
System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
primes.length, MAXN);
for (int i = 0; i < primes.length; i++)
System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
}
}
Testowanie dużej tablicy można wykonać w ten sposób:
import java.util.*;
public class BatchTest {
private static final Random rand = new Random();
public static int MIN_NUMBER = 1;
private final int minNumber = MIN_NUMBER;
private final int numberCount;
private final int[] numbers;
private int missingCount;
public long finderTime;
public BatchTest(int numberCount) {
this.numberCount = numberCount;
numbers = new int[numberCount];
for (int i = 0; i < numberCount; i++)
numbers[i] = minNumber + i;
}
private int passBound() {
int mBound = missingCount > 0 ? missingCount : 1;
int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
return Math.min(mBound, nBound);
}
private void error(String cause) {
throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
}
// returns the number of times the input array was traversed in this test
public int makeTest(int missingCount) {
this.missingCount = missingCount;
// numbers array is reused when numberCount stays the same,
// just Fisher–Yates shuffle it for each test
for (int i = numberCount - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
if (i != j) {
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}
}
final int bagSize = numberCount - missingCount;
NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
finderTime -= System.nanoTime();
int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
finderTime += System.nanoTime();
if (inputBag.getPassCount() > passBound())
error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
if (found.length != missingCount)
error("wrong result length");
int j = bagSize; // "missing" part beginning in numbers
Arrays.sort(numbers, bagSize, numberCount);
for (int i = 0; i < missingCount; i++)
if (found[i] != numbers[j++])
error("wrong result array, " + i + "-th element differs");
return inputBag.getPassCount();
}
public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
BatchTest t = new BatchTest(numberCount);
System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
int minPass = Integer.MAX_VALUE;
int passSum = 0;
int maxPass = 0;
t.finderTime = 0;
for (int j = 1; j <= repeats; j++) {
int pCount = t.makeTest(missingCount);
if (pCount < minPass)
minPass = pCount;
passSum += pCount;
if (pCount > maxPass)
maxPass = pCount;
}
System.out.format("║ %9d %9d ║ %2d %5.2f %2d ║ %11.3f ║%n", missingCount, numberCount, minPass,
(double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
}
}
public static void main(String[] args) {
System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
System.out.println("║ Number count ║ Passes ║ Average time ║");
System.out.println("║ missimg total ║ min avg max ║ per search (ms) ║");
long time = System.nanoTime();
strideCheck(100, 0, 100, 1, 20_000);
strideCheck(100_000, 2, 99_998, 1_282, 15);
MIN_NUMBER = -2_000_000_000;
strideCheck(300_000_000, 1, 10, 1, 1);
time = System.nanoTime() - time;
System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
}
}
Wypróbuj je na Ideone