这个代码的时间和空间复杂度是多少?
这里,是将任何数组的所有负元素移动到数组末尾,同时保持所有非负元素和负元素顺序的代码,如,
输入:{-11、-1、3、24、-7、-5、11、-6}
输出:{3、24、11、-11、-1、-7、-5、-6}
public static void MoveNegativeElementsToEnd(int arr[])
{
int k=arr.length-1;
int n=arr.length;
for(int i=n-1;i>=0;i--){
if(arr[i]<0){
for(int j=i;j<k;j++){
swap(arr,j,j+1);
}
k--;
}
}
}
public static void swap(int[] arr, int a, int b){
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
时间复杂度是O(N^2)
n -〉用于遍历数组
n -〉,用于每次将负元素交换到末尾。对吗?
空间复杂度是O(1)吗,对于所有的输入,它需要相同数量的变量?
1条答案
按热度按时间xwbd5t1u1#
内部循环运行
n-1-i
次(当它运行时),假设数组元素的概率p
为负,每个元素贡献p(n-1-i)
个交换,现在将i
在[n-1, 0]
中求和,即n-1-i
在[0, n-1]
中求和,预期成本为互换。