数组以n分为大于小于n的左右两部分

给定一个数组arr，和一个数num，请把小于等于num的数放在数 组的左边，大于num的数放在数组的右边。 要求额外空间复杂度O(1)，时间复杂度O(N)
思路：两个指针

void part_num(int arr[], int num, int len){
//方法1
	int pre = -1;
	int now = 0;
	while (now < len){
		if (arr[now] < num){
			if (++pre != now)
				swap(arr[pre], arr[now]);
		}
		++now;
	}
}
void part_num2(int arr[], int num, int len){
//方法1
	int left = 0;
	int right = len - 1;
	while (left < right){
	//边界问题容易出错
		while (arr[left] < num&&left<right)
			left++;
		while (arr[right]>=num&&right>left)
			right--;
		swap(arr[left++], arr[right--]);
	}
}

问题二（荷兰国旗问题） 给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。 要求额外空间复杂度O(1)，时间复杂度O(N)

类似于上面两种方法的综合，一边找大的，一边找小的不

void part_num3(int arr[], int num, int len){
	int less = -1;
	int more = len;
	int now = 0;
	while (now<more){
		if (arr[now] < num)
			swap(arr[++less], arr[now++]);
		else if (arr[now]>num)
			swap(arr[--more], arr[now]);//注意now不能++这里
		else
			++now;
	}
}

最后

以上就是虚幻小刺猬为你收集整理的数组以n分为大于小于n的左右两部分的全部内容，希望文章能够帮你解决数组以n分为大于小于n的左右两部分所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。