zkaiwen
BAN USERYou can do it in O(n) time and O(n) space. For each index, swap the current index in A with the index specified in B. If the current index has been swapped to before, skip. The indices that were swapped to can be kept in a hash table for O(1) look up. Here's a c++ code for it.
include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <set>
void sort(std::vector<char>& a, std::vector<int>& b){
std::set<int> swapped; //using a set, but ideally, a hash table for O(1) lookup
if(a.size() == b.size()){
for(unsigned int i = 0; i < a.size(); i++){
if(swapped.find(i) == swapped.end()){
char temp = a[b[i]];
a[b[i]] = a[i];
a[i] = temp;
swapped.insert(b[i]);
}
}
}
}
int main(){
std::vector<char> a;
a.push_back('C');
a.push_back('D');
a.push_back('E');
a.push_back('F');
a.push_back('G');
std::vector<int> b;
b.push_back(3);
b.push_back(0);
b.push_back(4);
b.push_back(1);
b.push_back(2);
sort(a, b);
for(unsigned int i = 0; i < a.size(); i++)
printf("%c, ", a[i]);
printf("\n");
return 0;
}
I think for worst case this would be O(N^2), not O(N). This is because if you have
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,99], 100, the first time you have to check n numbers, then the second you check n-1 numbers and essentially won't find a result until you hit the last two, which ends up being O(N^2)
Here's my solution using stack
- zkaiwen April 13, 2017