Question

求满足一下条件的算法，时间复杂度为O(n)

有一个数组a={n1,n2,.........n}共n个，
设计一个算法，将该数组分成两部分且返回分界点的下标a[?]，第一个部分的所有数据的值均小于分界点处的值，第二个部分的所有数据的值均大于分界点处的值。（类似于快速排序的第一轮），要求：算法的时间复杂度为O(n)，

若以下回答无法解决问题，邀请你更新回答

Answer 1

对着自己的数据类型做相应地修改：
void Delete(SeqList L, DataType x)
{ // 顺序表的删除算法
int i = 0, j;
for (j = 0; j < L->length; j ++)
if (L->data[j] != x)
{
if (i < j)
L->data[i] = L->data[j];
i ++;
}
L->length = i;
}

void Delete_List(LinkList head, DataType x)
{ // 有头结点单链表的删除算法
Node *p, *q, *s;
p = head->next;
q = head;
while (p != NULL)
{
if (p->data != x)
q = p;
else
{
s = p;
q->next = s->next;
free(s);
}
p = q->next;
}
}