/**
* For every number num, if it is not in the right seat, send it home, mark the seat as empty by 0;
* If its seat is occupied by another number other, send the other home;
* If its seat is occupied by a same number, it is duplicate.
* scan the array for 0, means empty seat;
*/
class Solution {
public:
vector<int> findErrorNums(vector<int>& a) {
vector<int> res(2);
int n = a.size();
for (int i = 0; i < n; i++) {
if (a[i] != i + 1 && a[i] != 0) {
int j = i;
int k = a[j];
a[j] = 0;
while (k != j + 1) {
j = k  1;
// dup
if (a[j] == 0) {
a[j] = k;
}
else if (a[k  1] == k) {
res[0] = k;
}
else {
int other = a[j];
a[j] = k;
k = other;
}
}
}
}
// scan the array for 0, means empty seat;
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
res[1] = i + 1;
break;
}
}
return res;
}
};
[C++] Solution O(1) space O(N) time


This is an 6 lines version: https://discuss.leetcode.com/topic/97091/6linescsolutionwithexplanation.