Skip to Content
CTRL K

Mex Min

Explicación

Podemos usar una ventana deslizante para llevar la cuenta de los MM elementos que no se pueden excluir. Para rastrear los elementos excluidos, podemos guardar todos los enteros de 00 a NN en un conjunto y reportar el valor más bajo del conjunto para cada ventana. Se usa una tabla de frecuencias para llevar la cantidad de apariciones de un elemento en la ventana, a fin de determinar cuándo hay que quitarlo o agregarlo al conjunto de excluidos.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <climits>
#include <iostream>
#include <set>
#include <vector>
 
using namespace std;
 
int main() {
	int n, m;
	cin >> n >> m;
 
	set<int> s;
	for (int i = 0; i <= n; i++) { s.insert(i); }
	vector<int> v(n);
	for (int i = 0; i < n; i++) { cin >> v[i]; }
 
	int res = INT_MAX;
	vector<int> window_freq(n);
	for (int i = 0; i < n; i++) {
		if (i < m) {
			s.erase(v[i]);
			window_freq[v[i]]++;
		} else {
			res = min(res, *s.begin());
			window_freq[v[i]]++;
			s.erase(v[i]);
			window_freq[v[i - m]]--;
			if (window_freq[v[i - m]] == 0) { s.insert(v[i - m]); }
		}
	}
 
	cout << min(res, *s.begin()) << endl;
}
import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); }
 
		TreeSet<Integer> s = new TreeSet<>();
		for (int i = 0; i <= n; i++) { s.add(i); }
 
		int[] windowFreq = new int[n];
		int res = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			if (i < m) {
				s.remove(arr[i]);
				windowFreq[arr[i]]++;
			} else {
				res = Math.min(res, s.first());
				s.remove(arr[i]);
				windowFreq[arr[i]]++;
				int old = arr[i - m];
				windowFreq[old]--;
				if (windowFreq[old] == 0) { s.add(old); }
			}
		}
 
		System.out.println(Math.min(res, s.first()));
	}
}
from bisect import bisect_left, insort
 
n, m = map(int, input().split())
arr = list(map(int, input().split()))
 
s = list(range(n + 1))
present = [True] * (n + 1)
window_freq = [0] * (n)
res = float("inf")
 
for i in range(n):
	if i < m:
		if present[arr[i]]:
			s.pop(bisect_left(s, arr[i]))
			present[arr[i]] = False
		window_freq[arr[i]] += 1
	else:
		res = min(res, s[0])
		if present[arr[i]]:
			s.pop(bisect_left(s, arr[i]))
			present[arr[i]] = False
		window_freq[arr[i]] += 1
		old = arr[i - m]
		window_freq[old] -= 1
		if window_freq[old] == 0:
			if not present[old]:
				insort(s, old)
				present[old] = True
 
print(min(res, s[0]))

Solución alternativa

Podemos hacer una observación que elimina la necesidad de llevar realmente la cuenta de la ventana. Un elemento puede excluirse de la ventana por dos razones:

  • Hay un hueco de tamaño al menos MM entre dos apariciones del mismo número.
  • El elemento no aparece en absoluto. Así, podemos llevar la última posición vista de cada elemento y determinar si alguna vez hay un hueco de tamaño MM entre las dos posiciones. Después, comparamos cada última posición vista con el extremo, tanto para comprobar la distancia al final como la existencia.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	int n, m;
	cin >> n >> m;
 
	vector<int> v(n);
	for (int i = 0; i < n; i++) { cin >> v[i]; }
 
	vector<int> last_seen_pos(n + 1, -1);
	vector<bool> valid(n + 1);
 
	for (int i = 0; i < n; i++) {
		if (i - last_seen_pos[v[i]] > m) { valid[v[i]] = true; }
		last_seen_pos[v[i]] = i;
	}
 
	// comparamos el extremo con last_seen_pos
	// esta comprobación también asegura que los elementos que no aparecen se consideren válidos
	for (int i = 0; i <= n; i++) {
		if (n - last_seen_pos[i] > m) { valid[i] = true; }
	}
 
	for (int i = 0; i <= n; i++) {
		if (valid[i]) {
			cout << i << endl;
			break;
		}
	}
}
import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(" ");
		int n = Integer.parseInt(nm[0]);
		int m = Integer.parseInt(nm[1]);
 
		int[] nums = new int[n];
		String[] vals = br.readLine().split(" ");
		for (int i = 0; i < n; i++) { nums[i] = Integer.parseInt(vals[i]); }
 
		int[] lastSeenPos = new int[n + 1];
		Arrays.fill(lastSeenPos, -1);
		boolean[] valid = new boolean[n + 1];
 
		for (int i = 0; i < n; i++) {
			if (i - lastSeenPos[nums[i]] > m) { valid[nums[i]] = true; }
			lastSeenPos[nums[i]] = i;
		}
 
		for (int i = 0; i <= n; i++) {
			if (n - lastSeenPos[i] > m) { valid[i] = true; }
		}
 
		for (int i = 0; i <= n; i++) {
			if (valid[i]) {
				System.out.println(i);
				break;
			}
		}
 
		br.close();
	}
}
n, m = map(int, input().split())
nums = list(map(int, input().split()))
 
last_seen_pos = [-1] * (n + 1)
valid = [False] * (n + 1)
 
for i in range(n):
	if i - last_seen_pos[nums[i]] > m:
		valid[nums[i]] = True
	last_seen_pos[nums[i]] = i
 
for i in range(n + 1):
	if n - last_seen_pos[i] > m:
		valid[i] = True
 
for i in range(n + 1):
	if valid[i]:
		print(i)
		break
Fundamentos