Мне дали «Переставить данный массив так, чтобы Arr [i] стал Arr [Arr [i]] с O (1) дополнительным пробелом».
Мне дают вектор целого числа в качестве входных данных.
Пусть N будет количеством элементов в векторе.
Все элементы в массиве находятся в диапазоне [0, N-1].
N * N не переполняется для целого числа со знаком.
Ссылка: https://www.interviewbit.com/problems/rearrange-array/
Я попытался переместить исходное значение массива в верхнюю часть int, то есть от 16 до 32 бит (при условии 32-битного int в c ++), а затем добавить новые значения Arr [i] в нижнюю часть int, находится в битах от 0 до 15, так как мне было сказано, что «N * N не переполняется для целого числа со знаком», поэтому числа должны умещаться в половину пространства, предусмотренного для int в C ++.
void Solution::arrange(vector<int> &A) {
int n=A.size();
for(int i=0;i<n;i++){
A[i]<<=16; //original values are moves to higher bits
}
for(int i=0;i<n;i++)
{
int p = A[i]>>16; //get the position i.e. Arr[i] part of Arr[Arr[i]]
int v = A[p]>>16; //the value Arr[Arr[i]]
A[i]|=v; // bit-wise or the new value to move it to lower bits.
}
for(int i=0;i<n;i++)
{
A[i]&=65535; // upper bits from 16 to 32 are set to zero
}
}
Работает нормально для небольших входов, но показывает ошибку сегментации при отправке решения. Пожалуйста, помогите устранить ошибку сегментации.