You are viewing a single comment's thread. Return to all comments →
/* * Complete the 'almostSorted' function below. * * The function accepts INTEGER_ARRAY arr as parameter. */ void printVec(const vector<int>& v) { for (auto e: v) { cout << e << " "; } cout << endl; } int myswap(vector<int>& v, size_t i, size_t j) { int count = 0; while ((i < j) && (v[i] == j) && (v[j] == i)) { swap(v[i], v[j]); count++; i++; j--; } return count; } int check(const vector<int>& v) { for (size_t i = 0; i < v.size(); ++i) { if (v[i] != i) { return i; } } return -1; } void almostSorted(vector<int> arr) { size_t n = arr.size(); vector<int> ix(n); iota(ix.begin(), ix.end(), 0); sort( ix.begin(), ix.end(), [&arr](size_t i, size_t j) { return arr[i] < arr[j]; } ); // printVec(arr); // printVec(ix); int i = check(ix); if (i == -1) { cout << "yes" << endl; return; } size_t l = i; size_t r = ix[i]; // cout << "l=" << l << " r=" << r << endl; int count = myswap(ix, l, r); // cout << "count=" << count << endl; i = check(ix); if (i == -1) { if (count == 1) { cout << "yes" << endl; cout << "swap " << l+1 << " " << r+1 << endl; } else { cout << "yes" << endl; cout << "reverse " << l+1 << " " << r+1 << endl; } } else { cout << "no" << endl; } // printVec(ix); }
Seems like cookies are disabled on this browser, please enable them to open this website
Almost Sorted
You are viewing a single comment's thread. Return to all comments →