编写程序已知线性表(a1,a2, a3 ,…,an)按顺序存于内存,每个元素都是整数,试设计用最少时间把所有值为负数的元素移到全部非负数值元素前边的算法:例:(x,-x,-x,x,x,-x …x)变为(-x,-x,-x…x,x,x)。

解题思路：
可以使用两个指针，分别指向左右两端，左指针从左往右遍历，右指针从右往左遍历，当左指针指向的元素为正数，右指针指向的元素为负数时，交换两个元素，直到左指针和右指针相遇为止。

代码实现：

void moveNegative(int a[], int n) {
    int left = 0, right = n-1;
    while (left < right) {
        while (a[left] < 0 && left < right) left++;
        while (a[right] >= 0 && left < right) right--;
        if (left < right) {
            int temp = a[left];
            a[left++] = a[right];
            a[right--] = temp;
        }
    }
}

时间复杂度：O(n)

相关问题

已知线性表（a1，a2，a3，…，an）每个元素都是整数，试用c语言设计该线性表的一种存储结构

线性表是一种常见的数据结构，它是由n个数据元素a1,a2,a3,...,an组成的有限序列。线性表的存储结构有两种：顺序存储和链式存储。在C语言中，可以使用数组来实现线性表的顺序存储结构。

具体实现方法如下：

#define MAXSIZE 100 // 定义线性表的最大长度

typedef struct {
    int data[MAXSIZE]; // 存储线性表元素的数组
    int length; // 线性表的当前长度
} SqList; // 定义顺序存储结构

// 初始化线性表
void InitList(SqList *L) {
    L->length = 0;
}

// 插入元素
int ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) {
        return 0; // 插入位置不合法
    }
    if (L->length >= MAXSIZE) {
        return 0; // 线性表已满
    }
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1]; // 将第i个元素及之后的元素后移
    }
    L->data[i - 1] = e; // 插入新元素
    L->length++; // 线性表长度加1
    return 1;
}

// 删除元素
int ListDelete(SqList *L, int i) {
    if (i < 1 || i > L->length) {
        return 0; // 删除位置不合法
    }
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j]; // 将第i个元素之后的元素前移
    }
    L->length--; // 线性表长度减1
    return 1;
}

三） 已知线性表按顺序存于内存，每个元素都是整数且无相同的，试设计算法用最少时间将所有值为负数的元素移到全部非负值前面。

要实现将线性表中所有负数元素移动到非负元素前面的算法，并且要求时间复杂度最低，可以采用双指针策略。以下是算法的基本思路：

1. 初始化两个指针，一个指针left指向数组的第一个元素，另一个指针right指向数组的最后一个元素。
2. 从数组的左端开始向右扫描，遇到负数时，与数组右端的元素交换（确保非负数移到右边）。每交换一次，left指针向右移动一位，right指针向左移动一位。
3. 重复步骤2，直到left指针和right指针相遇或者left指针超过right指针。

该算法的时间复杂度为O(n)，因为每个元素最多被交换一次。以下是算法的伪代码：

function reorganizeArray(arr):
    left = 0
    right = length(arr) - 1
    while left <= right:
        if arr[left] < 0:
            left += 1
        elif arr[right] >= 0:
            right -= 1
        else:
            swap(arr[left], arr[right])
            left += 1
            right -= 1

使用上述算法，可以高效地将所有负数移动到数组的前面，而所有非负数则移动到后面。