[已解决]编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)

Kitty喜欢小鱼干

/*----------------------本算法有误，请各位检查并帮助修改-------------------*/

//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。

//例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->  {-4, -1, -2, -1, 4, 1, 3, 2, 1}

#include <stdio.h>

void Func(int list[], int n){
    int i=0, j=n-1, temp, k;
    int *List;
    while( i < j ){
        while (list[i]<0) i++;
        while (list[j]>0) j--;

        if( list[i] > list[j] ){
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }
    }

    for( k=0; k<n; k++ ){
        List[k] = list[k];
        printf("%d", List[k]);
    }
    return;
}

int main(){
    int a[9] = {1, 2, 3, 4, -1, 1, -2, -1, -4};
    Func(a, 9);
    return 0;
}

最佳答案

月排行榜 / 总排行榜

人造人

2018-8-14 14:58:21

无符号整形 发表于 2018-8-14 17:00
额 你这个复杂度是O(n^2)了呀。

这次应该没问题了

//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。
//例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->  {-4, -1, -2, -1, 4, 1, 3, 2, 1}

#include <stdio.h>

void Swap(int *a, int *b)
{
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

void Fun(int data[], int len)
{
        int dest = 0;

        for(int i = 0; i < len; ++i)
        {
                if(data[i] < 0)
                {
                        Swap(&data[i], &data[dest++]);
                }
        }
}

void Print(int data[], int len)
{
        for(int i = 0; i < len; ++i)
        {
                printf("%d ", data[i]);
        }
        printf("\n");
}

int main(void)
{
        int a[9] = {1, 2, 3, 4, -1, 1, -2, -1, -4};
        //Func(a, 9);
        Fun(a, 9);
        Print(a, 9);
        return 0;
}

跳转到最佳答案楼层

人造人

无符号整形 发表于 2018-8-14 17:00
额 你这个复杂度是O(n^2)了呀。

这次应该没问题了

//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。
//例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->  {-4, -1, -2, -1, 4, 1, 3, 2, 1}

#include <stdio.h>

void Swap(int *a, int *b)
{
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

void Fun(int data[], int len)
{
        int dest = 0;

        for(int i = 0; i < len; ++i)
        {
                if(data[i] < 0)
                {
                        Swap(&data[i], &data[dest++]);
                }
        }
}

void Print(int data[], int len)
{
        for(int i = 0; i < len; ++i)
        {
                printf("%d ", data[i]);
        }
        printf("\n");
}

int main(void)
{
        int a[9] = {1, 2, 3, 4, -1, 1, -2, -1, -4};
        //Func(a, 9);
        Fun(a, 9);
        Print(a, 9);
        return 0;
}

人造人

看不懂你的代码，我自己写了一个

//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。
//例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->  {-4, -1, -2, -1, 4, 1, 3, 2, 1}

#include <stdio.h>

#if 0
void Func(int list[], int n)
{
        int i = 0, j = n - 1, temp, k;
        int *List;

        while(i < j)
        {
                while(list < 0) i++;
                while(list[j] > 0) j--;

                if(list > list[j])
                {
                        temp = list;
                        list = list[j];
                        list[j] = temp;
                }
        }

        for(k = 0; k < n; k++)
        {
                List[k] = list[k];
                printf("%d", List[k]);
        }
        return;
}
#endif

void Swap(int *a, int *b)
{
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

void Fun(int data[], int len)
{
        for(int i = 0; i < len; ++i)
        {
                if(data[i] > 0)
                {
                        for(int j = i + 1; j < len; ++j)
                        {
                                if(data[j] < 0)
                                {
                                        Swap(&data[i], &data[j]);
                                        break;
                                }
                        }
                }
        }
}

void Print(int data[], int len)
{
        for(int i = 0; i < len; ++i)
        {
                printf("%d ", data[i]);
        }
        printf("\n");
}

int main(void)
{
        int a[9] = {1, 2, 3, 4, -1, 1, -2, -1, -4};
        //Func(a, 9);
        Fun(a, 9);
        Print(a, 9);
        return 0;
}

无符号整形

人造人 发表于 2018-8-14 16:08
看不懂你的代码，我自己写了一个

额 你这个复杂度是O(n^2)了呀。

人造人

无符号整形 发表于 2018-8-14 17:00
额 你这个复杂度是O(n^2)了呀。

O(n)就是一次循环
一次循环要如何完成这个功能？

无符号整形

人造人 发表于 2018-8-14 17:08
这次应该没问题了

好像对的……
我怎么没想到……

人造人

无符号整形 发表于 2018-8-14 17:10
好像对的……
我怎么没想到……

^_^

claws0n

人造人 发表于 2018-8-14 17:08
这次应该没问题了

负数值不对，还是我理解题目错了？?

人造人

claws0n 发表于 2018-8-14 17:33
负数值不对，还是我理解题目错了？?

//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。

claws0n

人造人 发表于 2018-8-14 17:37
//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。

我知道，但排序需不需要考虑？

人造人

claws0n 发表于 2018-8-14 17:47
我知道，但排序需不需要考虑？

这个题目没有要求排序

claws0n

人造人 发表于 2018-8-14 17:47
这个题目没有要求排序

好~~

Kitty喜欢小鱼干

人造人 发表于 2018-8-14 14:58
这次应该没问题了

谢谢！原来我最需要的其实是这一节代码。

void Print(int data[], int len)
{
        for(int i = 0; i < len; ++i)
        {
                printf("%d ", data);
        }
        printf("\n");
}