是否可以在一个解析之内按降序排列只有1和0的数组,而不使用辅助数组？
例如：假设你有一个数组a [] = {1,1,1},为此预期的输出将是一个[] = {1,0}.
例如：假设你有一个数组a [] = {1,1,1},为此预期的输出将是一个[] = {1,0}.
我写了下面的C代码,但是它在2个解析中找到了解.可以优化吗？
void arrange(int a[],int n) {
int i,count=0;
for(i=0;i<n;i++) {
if(a[i]==1)
count++;
a[i]=0;
}
for(i=0;i<count;i++) {
a[i]=1;
}
}
解决方法
让我试试这个：
void arrange(int a[],int n)
{
int* p = a;
int* q = &a[n-1];
while (p <= q)
{
while (*p == 1 && p <= q) /* Find a Zero,starting from the front */
{
++p;
}
while (*q == 0 && p <= q) /* Find a One,starting from the back */
{
--q;
}
if (p < q) /* *p == Zero,and *q == One,and p is to the left of q. */
{
*p = 1;
*q = 0;
}
}
}
这有两个指针,一个从前面开始,另一个从后面开始,他们都向中间移动,直到他们相遇.
一路上,如果两个指针在左边找到一个0,在右侧找到一个,交换值,然后继续.
(代码未经测试,但轮廓看起来很实在)
