leetcode刷题——排序和二分

发布于:2023-02-09 ⋅ 阅读:(633) ⋅ 点赞:(0)

目录

归并排序——分治

 练习题1 逆序对的数量

练习题2 合并俩个有序数组

 快速排序——分治

 二分——整数二分

浮点数二分 


归并排序——分治

 

共logn层,每层是O(n)

时间复杂度O(nlogn)

1.确定分界点,将数组按最中间的位置分开(下标的中间值)

2.递归排序左边和右边

3.左边和右边合二为一

俩个有序数组,用指针移动的方法进行比较,min1指针此时所指的数<min2指针此时所指的数,新建一个数组P存放数字1,然后min1指针加1,继续和min2指针所指数相比,比完之后最小值放到数组P中,以此类推

这种情况当min1指针走到数组末尾时,把min2指针所指的数及其余的数全部放到数组P

 

参考代码:

void merge_sort(int* arr, int l, int r)
{
	if (l >= r)
		return;
	int mid = (l + r) / 2;
	merge_sort(arr, l, mid );
	merge_sort(arr, mid+1, r);
	int tmp[100];
	int i = l;
	int j = mid + 1;
	int k = 0;
	while (i <= mid&&j<=r)
	{
		if (arr[i] < arr[j])
			tmp[k++] = arr[i++];
		else
			tmp[k++] = arr[j++];
	}
	while (i <= mid)
		tmp[k++] = arr[i++];
	while (j <= r)
		tmp[k++] = arr[j++];

	for (i = l,j=0; i <=r; i++,j++)
	{
		arr[i] = tmp[j];
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	int arr[100];
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	merge_sort(arr, 0, n-1);
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

 练习题1 逆序对的数量

给定一个长度为 nn 的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 ii 个和第 jj 个元素,如果满足 i<ji<j 且 a[i]>a[j]a[i]>a[j],则其为一个逆序对;否则不是。

输入:6
            2 3 4 5 6 1

输出:5

主要思想:

先给俩边按从小到大顺序排序,当指针l所指元素大于指针j时,由于数组左右半边数组都是有序的说明l前面的元素都小于j所指元素,而l到mid,[l,mid]内的元素都大于j,因此逆序对数为:ret=mid-l+1。

#include<stdio.h>
static long long ret = 0;
long long merga_sore(int* arr, int l, int r)
{
    if (l >= r)
        return 0;
    int mid = (l + r) / 2;

    merga_sore(arr, l, mid); merga_sore(arr, mid + 1, r);
    int i = l;
    int tmp[100000];
    int k = 0;
    int j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
        {
            tmp[k++] = arr[j++];
            ret += (mid - i + 1);
        }
    }
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];
    for (i = l, j = 0; i <= r; i++, j++)
    {
        arr[i] = tmp[j];
    }
    return ret;
}
int main()
{
    int arr[100000];
    int n;
    int i;
    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%d", &arr[i]);
    long long c = merga_sore(arr, 0, n - 1);
    printf("%lld", c);
    return 0;
}

 这里采用C代码解题

练习题2 合并俩个有序数组

点这里跳转

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
 int i=m-1;
 int j=n-1;
 int k=m+n-1;
 while(i>=0&&j>=0)
 {
     if(nums1[i]>nums2[j])
         nums1[k--]=nums1[i--];
      
     else
          nums1[k--]=nums2[j--];
 }
 while(i>=0)
  nums1[k--]=nums1[i--];
  while(j>=0)
   nums1[k--]=nums2[j--];
   return (m+n-1);
}

 比较end1和end2所指的元素,将较大元素放入k所指地址中,较小元素站在原地不动,等一个数组遍历结束后,另一个数组就是较小值,较小值放前面就行

 快速排序——分治

 

1.确定分界点,q[left],q[right],q[(left+right)/2],随机值

2.调整区间,小于等于X的在X左边,大于等于X的在X右边

3.递归处理左右俩边,对左右俩边各进行排序

如何进行第二步?

方法1(暴力法):创建俩个数组a[]和b[],把<=x的元素放到a,>=x的元素放到b,然后把a数组放到q中,b也放到q中

方法2(双指针):使用俩个指针,分别从左端点和右端点开始遍历数组,当左端点遇到>=x的元素时,左指针不再进行移动,此时左指针指向>=x的元素,然后等右端点遇到<=x的元素时,此时将这俩个元素进行交换,交换完之后俩指针继续往中间移动,同样的右端点若先遇到<=x的元素,则右端点停止遍历,在原地等左端点即可

用3作为分界点,此时left=3则left指针停止前进,right满足>3,right向中间靠拢

right此时不再满足>3,right停止前进,此时交换right和left所指向的俩个元素,交换完之后,各自向中间靠拢

left所指元素满足<3,right所指元素不满足>3,right停止前进,left继续遍历

left已经>right了,此时就不能交换俩个数,我们这个时候可以发现 <=3的在左边,>=3的在右边

#include<stdio.h>
void quick_qsort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int i = left-1;
	int j = right+1;
	int x = arr[left];
	while (i < j)
	{
		do
		{
			i++;
		} while (arr[i] < x);
		do
		{
			j--;
		} while (arr[j] > x);
		if (i < j)
		{
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
	}
    		quick_qsort(arr, 0, j);
		quick_qsort(arr, j+1, right);
}
int main()
{
	int arr[50];
	int n;
	scanf("%d", &n);
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	quick_qsort(arr, 0, n - 1);
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

注:当quick_qsort(arr, 0, j);函数里面为j时,x不能为arr[right],函数里面为i时,x不能为arr[left],这是边界问题,不然会陷入死循环

当x=arr[left],qsort函数传参为i时,若给1,2排序,让x=1,i=left-1=-1,j=2-1+1=2; 之后i++,i=0,arr[0]=1,不满足<x,j--,j=1,arr[1]=2,满足>x,然后j--,俩个都指向了1,j和i此时都是0,后面还有quick_qsort(arr, left, i-1);quick_qsort(arr, i, right);这俩个语句都是[0,1],会陷入死循环,当x=arr[right],qsort函数传参为j时,也会陷入死循环

时间复杂度nlog(n),共logn层,每层是O(n)

 二分——整数二分

整数二分:如果有单调性可以二分,部分没单调性的也可以二分

本质:一个数组在绿色部分满足某种性质,在红色部分不满足,我们可以通过二分找到红色和绿色的边界点

这里以红色为例

1.找一个中间值mid=(l+r+1)/2

2.判断这个中间值是否满足性质,看mid是否满足红色性质,若满足红色部分的性质,则mid在红色区域内,答案可能在[mid,r]中,因此让l=mid,

当mid不满足红色性质,mid在绿色区域内,答案在[l,mid-1],之后让r=mid-1

以绿色为例

观察上式,l=mid,需要补1,r=mid不需要补1

#include<stdio.h>
int main()
{
    int n;
    int m;
    scanf("%d%d", &n, &m);
    int i = 0;
    int arr[100000];
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    int k = 0;
​
    while (m--)
    {
        scanf("%d", &k);
        int l=0;
        int r=n-1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(arr[mid]>=k)
            r=mid;
            else
            l=mid+1;
        }
        if(arr[l]!=k)
        printf("-1 -1");
        else
        {
            printf("%d ",l);
            int l=0;
            int r=n-1;
            while(l<r)
            {
                int mid=(l+r+1)/2;
                if(arr[mid]<=k)
                l=mid;
                else
                r=mid-1;
            }
            printf("%d ",l);
        }
        printf("\n");
    }
    return 0;
}

总结:从前面往后面判断k的位置,if(arr[mid]>=k),先判断k在不在前面,若不在前面,则往后找,找出来之后再对第二个k进行查找,if(arr[mid]<=k),此时从k在不在后面判断,若不在后面则往前找,这样查找会避免重复查找

浮点数二分 

浮点数二分不需要严格的处理边界,保证答案落在区间内

当区间长度很小的时候,就可以当作答案,相当于估读

1.先求一个浮点数的平方根

2.每次找中间点(在0-x)

3.如果mid*mid>=x,则说明,mid在根号x和x区间内,让r=mid,否则l=mid,之后打印就行

本文含有隐藏内容,请 开通VIP 后查看