[일반] 빠진 숫자 찾는 알고리즘 아이디어좀

[익명(223.38)]

배열 하나 주어지고

1~n까지 빠진 숫자가 뭐뭐 있나 찾는건데

배열이 정렬된 상태는 아님

예를 들어 n=5 이고, [1, 5, 3] 이면 2, 4가 출력되게?

오버헤드도 적고 속도도 괜찮은 방법있을까? 

[익명(211.36)]

방문배열 n짜리 만들고 미방문시 출력 - dc App

[익명(14.33)]

int mp[2000001]; for (int i: ar) ++mp[i]; for (int i = 0; i < 2000001; ++i) if (!mp[i]) cout << i << ' ';

[Glacier(yoooo9)]

bool vis[N] 만들어놓고 배열 다 돌면서 방문했으면 false로 바꿔준다음 vis[N] 돌면서 true 다 출력

[ㅁ(119.202)]

memo할수있으면 그게 제일 직관적이고 만약 메모리를 O(1)로 써야해서 메모를 못한다면 주어진 숫자 다 더하고 N(N+1)/2에서 더한값을 빼는 방법이 있음

[ㅁ(119.202)]

아 그러네

[교수(218.239)]

1+2+...n = n(n+1)/2, 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6 이용하면 빠진 두 수를 u, v라 할 때 u+v, u^2+v^2 알 수 있고 여기서 uv 구할 수 있음. 이차방정식 t^2-(u+v)t+uv=0의 두 근이 u, v