1 题目

/**
 *  (2018吉林大学941)一个长度为 n 的数组由负数、0、正数组成。编写函数，将其重新排序为前段都是负数，后段均为非负数的结构。
 *  要求时间复杂度为 O(n)。
 */

2 题解

2.1 法一

2.1.1 解题思路

设置双指针，通过将负值与头指针交换，正值与尾指针交换，最终可以形成一个左负右正中间零的顺序表。

其中，需要理解的是头尾指针的移动以及遍历顺序表的索引值i如何自增。

i从第0个位置开始扫描顺序表。

若正，与尾指针交换，此时i不自增。因为还不能知道交换来的这个数是正是负。

若为0，则i自增。

若负，与头指针交换，此时i可自增。因为前面扫到的正数都抛到后面去了，前面不会出现正数。

可以发现，当头指针向后移动或者尾指针向前移动时，其实就是确定了一个元素的最终位置。

2.1.2 过程

程序验证：

2.1.3 结果

2.1.4 结果分析

时间复杂度O(n)，空间复杂度O(1)

2.1.5 代码

void switch_arr(int arr[],int len){
    int head = 0;
    int rear = len - 1;
    int count = 0;
    int i = 0;
    while (count < len){
        if(arr[i] < 0){
            _swap(arr, i, head);
            head++;
            i++;
            count++;
        }else if(arr[i] == 0){
            i++;
            count++;
        }else if(arr[i] > 0){
            _swap(arr, i, rear);
            rear--;
            count++;
        }
//        cout<<"过程数组：";
//        print_arr(arr,len);
    }
}

2.2 法二

2.2.1 解题思路

牺牲空间换时间，直接开辟另外一个数组填入数值即可。这里也需要左右指针。

2.2.2 过程

比较简单，这里省略了。

2.2.3 结果

2.2.4 结果分析

时间复杂度O(n)，空间复杂度O(n)

2.2.5 代码

int* switch_arr_2(int arr[],int len){
    int* copy_arr = (int*)malloc(sizeof (int) * len);
    int head = 0;
    int rear = len-1;
    for (int i = 0; i < len; ++i) {
        if(arr[i]<0){
            copy_arr[head++] = arr[i];
        }else if(arr[i]>0){
            copy_arr[rear--] = arr[i];
        }
    }
    for (int i = head; i <= rear; ++i) {
        copy_arr[i] = 0;
    }
    return copy_arr;
}