重新排列数组，使arr[i] =i
重新排列数组，使arr[i] =i
提问于 2018-06-06 03:33:27
Input : arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
Output : [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
Input : arr = {19, 7, 0, 3, 18, 15, 12, 6, 1, 8,
11, 10, 9, 5, 13, 16, 2, 14, 17, 4}
Output : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19]逼近 1.考虑数组。
- 检查ai = -1，如果是，则忽略它。
- 如果ai = -1，请检查元素ai是否位于其位置(i=Ai)。如果是，那就忽略它。
- 如果ai = -1并且ai不在它的位置(i != Ai)，那么将它放置到正确的位置，但是有两个条件： (i).Either Ai是空的，意思是Ai = -1，然后把Ai =i。 (ii).OR Ai不是空的，意思是Ai = x，然后int y=x put Ai = i。现在，我们需要把y放在它的位置，所以从步骤3开始重复。
下面的解决方案的时间复杂度是多少？
public static int[] fix(int[] A) {
for (int i = 0, x = A[i]; i < A.length; i++) {
if (x == -1 || x == i)
continue;
// check if desired place is not vacant
while (A[x] != -1 && A[x] != x) {
int y = A[x]; // store the value from desired place
A[x] = x; // place the x to its correct position
x = y; // now y will become x, now search the place for x
}
A[x] = x; // place the x to its correct position
// check if while loop hasn't set the correct value at A[i]
if (A[i] != i)
A[i] = -1; // if not then put -1 at the vacated place
}
return A;
}回答 2
Stack Overflow用户
发布于 2018-06-06 06:13:13
我可以给你提供两种算法。
第一个:使用额外数组的，时间复杂度是O(n)，有O(n)附加内存
public static int[] fix(int[] arr) {
int[] res = new int[arr.length];
Arrays.fill(res, -1);
for (int i = 0; i < arr.length; i++)
if (arr[i] != -1)
res[arr[i]] = arr[i];
return res;
}第二种：就位，时间复杂度在最坏的情况下是O(n^2)，而在平均情况下是O(n)，没有额外的内存。
public static int[] fix(int[] arr) {
int i;
while ((i = findIncorrectPosition(arr)) >= 0) {
while (arr[i] != -1 && arr[i] != i) {
swap(arr, i, arr[i]);
}
}
return arr;
}...plus两种私有支持方法：
private static int findIncorrectPosition(int[] arr) {
for (int i = 0; i < arr.length; i++)
if (arr[i] != -1 && arr[i] != i)
return i;
return -1;
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}Stack Overflow用户
发布于 2021-06-29 07:13:41
f(n) = O(n)使用交换方法#Swift
for i in stride(from: 0, to: array.count, by: 1){
if(array[i] >= 0 && array[i] != i){
let ele = array[array[i]]
array[array[i]] = array[i]
array[i] = ele
}
}
for k in stride(from: 0, to: array.count, by:1 ){
print(" ",array[k])
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50711876
复制相关文章
相似问题
腾讯云开发者
