1 c++ algorithm time-complexity
给出以下数组: | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
我们必须对上面的数组进行排序,就像右边的所有1和左边的0一样.
我在C++中提出了2种算法.
第一个:
for(i = 0; i < n; i++) {
if(a[i] == 1 && i != n - 1) {
for(j = i + 1; j < n; j++) {
if(a[j] == 0) {
temp = a[j];
a[i] = a[j];
a[j] = temp;
break;
}
}
}
}
Run Code Online (Sandbox Code Playgroud)
第二个:
int x = 0;
for(i = 0; i < n; i++) {
if(a[i] == 1) {
for(j = n-x-1; j >= 0; j--) {
if(a[j] == 0) {
temp = a[j];
a[i] = a[j];
a[j] = temp;
x++;
break;
}
}
if(x > n / 2)
break;
}
Run Code Online (Sandbox Code Playgroud)
你能告诉我两者的时间复杂度吗?哪一个表现更好也建议我一个更好的解释算法.谢谢.
Ale*_*sie 15
只需计算1的数量,然后用第一个lengthOfArray - sum元素和第一个元素重新填充数组.复杂性将是O(n).
在这两种情况下,你的复杂度都是O(n²)