精华内容
下载资源
问答
  • 寻找两个排序数组中K个,先从左边取K/2个,小的那一边的k/2都不可能是K个了,于是排除。 更新K=k-k/2,也就是在剩下的数组中,找到 新K的数字。 直到K==1,那么当前还剩余的数组中开头处偏小的。 就...

    题目描述

    在这里插入图片描述


    一、思路

    最简单的思路就是从两个数组头/尾开始归并的计数。但是这样时间复杂度0(m+n);并不满足要求。

    我们利用二分查找 log 时间复杂度的优势。只要单调就能二分

    即:

    1. 寻找两个排序数组中第K个数,先从左边取K/2个数,小的那一边的k/2都不可能是第K个数了,于是排除。
    2. 更新K=k-k/2,也就是在剩下的数组中,找到第 新K的数字。
    3. 直到K==1,那么取当前还剩余的数组中开头处偏小的。

    在这里插入图片描述
    就像上图:

    1. 找第7个元素,那么两个指针都指向k/2 = 3 的位置。
    2. 3<4,说明B中前三个肯定不能是第7个元素。
    3. 抛掉B中前三个,我们开始在剩下的元素中,找第4个了。
    4. 3<5,说明A中前两个也肯定不是剩下的里面第4个元素。
    5. 抛掉A中前两个,我们开始在剩下的元素中,找第2个了.
    6. 4<=4,随便抛掉一个4,我们从剩下的元素中找第1个。
      10.4<9,说明我们要的中位数就是4

    这么看起来是不是和最简单的归并计数下来差不多,只是每次舍弃的多了些而已。

    二、难点:

    1、中位数:和是奇数和是偶数怎么办

    就像上面的图。13个数据,中位数就是第7个数。

    如果是14个数,那么就找一下第七个数,然后再顺着找第八个数。然后取平均即可。

    三、代码

    class Solution {
    public:
    	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
    		int length = nums1.size() + nums2.size();
    
    		int k = (length+1) >> 1;
    		bool first =true;
    		if (length & 1)
    			first = false;
    		int temp,temp2=0;
    		//find NO.K
    		int base1 = 0, base2 = 0;
    		int offset1 = 0, offset2 = 0;
    		while (1)
    		{
    			offset1 = offset2 = (k >> 1);
    
    			if (base1 == nums1.size())
    			{
    				temp = nums2[base2 + k-1];
    				base2+= k ;
    				break;
    			}
    			else if (base2 == nums2.size())
    			{
    				temp = nums1[base1 + k-1];
    				base1+= k ;
    				break;
    			}
    			else if (base1 + offset1 -1>= (int)nums1.size())
    			{
    				offset1 = nums1.size() - base1;
    				offset2 = k - offset1;
    			}
    			else if (base2 + offset2 -1>= (int)nums2.size())
    			{
    				offset2 = nums2.size() - base2;
    				offset1 = k - offset2;
    			}
    
    			if (k == 1)
    			{
    				if (nums1[base1 + offset1] <= nums2[base2 + offset2])
    				{
    					temp = nums1[base1 + offset1];
    					base1++;
    				}
    				else
    				{
    					temp = nums2[base2 + offset2];
    					base2++;
    				}
    					break;
    			}
    
    			if (nums1[base1 + offset1 - 1] <= nums2[base2 + offset2-1])
    			{
    				base1 += offset1;
    				k -= offset1;
    			}
    			else
    			{
    				base2 += offset2 ;
    				k -= offset2;
    			}
    
    		}
    		if (length & 1)
    			return temp;
    		else
    		{
    			if (base1 == nums1.size())
    			{
    				temp += nums2[base2];
    
    			}
    			else if (base2 == nums2.size())
    			{
    				temp += nums1[base1];
    
    			}
    			else
    				temp+= min(nums1[base1], nums2[base2]);
    			return temp / 2.0;
    		}
    			
    	}
    };
    

    考察的点:

    1. 二分查找
    2. 归并
    展开全文
  • 排序准备:取左边第一位数为pivot轴,即pivot = a[0], 再令left = a[0],right = a[N-1] 排序过程:此时右端(right)开始,比较right对应的 与pivot轴的大小,如果右边比pivot大(a[right] > pivot) 下标左移...

    快速排序C语言版(附带视频讲解)

    注:3种快排的名字是我自己取的,并非专业名称

    方法一(最常用的方法):左端抽轴(pivot)法

    思路 && 操作:

    1. 排序准备:取左边第一位数为pivot轴,即pivot = a[0],
      再令left = a[0],right = a[N-1]
    2. 排序过程:此时从右端(right)开始,比较right对应的数
      与pivot轴的大小,如果右边比pivot大(a[right] > pivot)
      下标左移(right–),反之,将a[right]放在a[left]位置
    3. 完成一次操作(PartSort())循环结束条件为:left != right
    4. 递归函数进入条件:left < right

    视频讲解:请点击->动画

    代码如下:

    
    #include <stdio.h>
    #define N 15
    
    int PartSort(int * a, int left, int right);
    void QuickSort(int * a, int left, int right);
    void Print(int * a);
    
    int main(void)
    {
    	int i, a[N] = {5, 8, 1, 7, 4, 9, 48, 14, 0, 99, 45, 2, 84, 65, 6};
    
    	printf("Before sort:\n");
    	Print(a);
    	printf("\nAfter sort:\n");
    	QuickSort(a, 0, N-1);
    	Print(a);
    	
    	return 0;
    }
    
    int PartSort(int * a, int left, int right)
    {
    	int pivot = a[left];
    	while (left != right)
    	{
    		while (left < right && a[right] >= pivot)
    		   right --;
    		a[left] = a[right];
    		while (left < right && a[left] <= pivot)
    		   left ++;
    		a[right] = a[left];
    	}
    	a[left] = pivot;
    	
        return left;
    }
    
    void QuickSort(int * a, int left, int right)
    {
    	int mid = 0;
    	
    
    	if (left < right)
    	{
    	   mid = PartSort(a, left, right);
    		QuickSort(a, left, mid-1);
    		QuickSort(a, mid+1, right);
    	}
    	
    	return;
    }
    
    void Print(int * a)
    {
    	int i;
    	for (i = 0; i < N; i ++)
    	   printf("%d ", a[i]);
    	printf("\n");
    	
    	return;
    }
    

    运行结果如下:
    devc++运行结果
    方法二:右端基准(basic)法

    思路 && 操作:

    1. 排序准备:选取最右端数字为basic(基准),最左端标记为L(left),
      右端倒数第二个数标记为R(right)
    2. 排序过程:从左端开始,L指向的数比basic所指数小,则L向后移动一位(left++)
      否则则停下;后,右端开始出发,如果R所指向的数字比basic大,则R向前移动
      一位(right–),直到R也停下,此时将二者对应的数字进行交换,L后移,R前移
      各一位完毕后,再从左端开始重复以上操作
    3. 完成一次操作(PartSort())循环结束条件为 :left < rigt(而非left != rigt)
      因为数字交换导致的L和R分别进位可能会导致二者"擦肩而过",永世不得相遇
    4. 递归函数进入条件为:left < right 代码如下

    视频讲解:请点击->动画

    注:该视频所讲述略有瑕疵,视频中说L(left)与R(right)相遇后,L与R所指的同一个数(a)要与basic基准交换。实际上,交不交换取决于该数(a)与basic的大小,如果该数(a)大于basic基准,肯定要作交换,但是反之,就不能直接交换了,需要用该数(a)的下一个数与basic交换,想想为什么

    举个例子:3 2 1 5(basic) —进行操作— 3 2 1 5(basic)

    ​ L R ----doing… — L&R

    这个时候1 就不能和 5 换位置,换了就变成 3 2 5 1,1比5小怎么在5右侧?

    实际上:每一次的basic的轴都是将一组数分割成两组的中心轴!

    代码如下:

    #include <stdio.h> 
    #define N 15 
    
    void Swap(int * a, int left, int basic);
    int PartSort(int * a, int left, int right);
    void QuickSort(int * a, int left, int right);
    void Print(int * a);
    
    int main(void)
    {
    	int a[N] = {5, 8, 1, 7, 4, 9, 48, 14, 0, 99, 45, 2, 84, 65, 6};
    
    	printf("Before sort:\n");
    	Print(a);
    	QuickSort(a, 0, N-1);
    	printf("\nAfter sort:\n");
    	Print(a);
    	
    	return 0;
    } 
    
    void Swap(int * a, int left, int  param)
    {
    	int temp;
    	temp = a[left];
    	a[left] = a[param];
    	a[param] = temp;
    
        return;
    }
    
    int PartSort(int * a, int left, int right)
    {
    	int basic = right --;
    	
    	while (left < right)
    	{
    		while (left < right && a[left] <= a[basic])
    		   left ++;
    		while (left < right && a[right] >= a[basic])
    		   right --;
    		if (left != right)  
    		{
    			Swap(a, left, right);
    			left ++;
    			right --;
    	    }
    		
    	}
    	if (a[left] > a[basic])  Swap(a, left, basic);
    	else  Swap(a, ++ left, basic);
    	
    	return left;
    }
    
    void QuickSort(int * a, int left, int right)
    {
    	int mid = 0;
    	
    	if (left < right)
    	{
    		mid = PartSort(a, left, right);
    		QuickSort(a, left, mid-1);
    		QuickSort(a, mid+1, right);
    	}
    	
    	return;
    }
    
    void Print(int * a)
    {
    	int i;
    	for (i = 0; i < N; i ++)
    	   printf("%d ", a[i]);
    	printf("\n");
    	return;
    }
    

    运行结果如下:
    devc++运行结果
    方法三:快慢指针(i,j)法

    思路 && 操作:

    1. 排序准备:快慢指针的构建,i为慢指针,j为快指针;取最右端为pivot轴
      指针初始位置为: j为最左端,i为j的前一位(没错,刚开始i不对应数字)
    2. 排序过程:如果快指针j对应的数字比pivot小,则慢指针i前进1位, 然后将
      快慢指针对应的值进行交换;如果快指针j对应的数字比pivot大,则慢指针i
      不动最后,将慢指针右1位的数字(即i+1)对应的数字与pivot轴进行交换
    3. 完成一次操作(PartSort())循环结束条件为:快指针小于pivot轴位置(即j < pivot)
    4. 递归函数进入条件:start < end

    视频讲解:请点击->视频

    代码如下:

    #include <stdio.h>
    #define N 15
    
    void QuickSort(int * a, int start, int end);
    int PartSort(int * a, int start, int end);
    void Swap(int * a, int i, int j);
    void Print(int * a);
    
    int main(void)
    {
    	int a[N] = {5, 8, 1, 7, 4, 9, 48, 14, 0, 99, 45, 2, 84, 65, 6};
    	
    	printf("Before sort:\n");
    	Print(a);
    	QuickSort(a, 0, N-1);
    	printf("\nAfter sort:\n");
    	Print(a); 
    	
    	return 0;
    } 
    
    void QuickSort(int * a, int start, int end)
    {
    	int mid = 0;
    	
       if (start < end)
    	{
    		mid = PartSort(a, start, end);
    		QuickSort(a, start, mid-1);
    		QuickSort(a, mid+1, end); 
    	} 
    	
    	return;
    }
    
    int PartSort(int * a, int start, int end)
    {
    	int i = start - 1;
    	int j = start, pivot = end;
    	
    	for (; j < end; j ++)
    	{
    		if (a[j] < a[pivot])
    		{
    			i ++;
    			Swap(a, i, j);
    		}
    	}
    	Swap(a, i + 1, pivot);
    	pivot = i + 1; 
    	
    	return pivot;
    }
    
    void Swap(int * a, int i, int j)
    {
    	int temp;
    	
    	temp = a[i];
    	a[i] = a[j];
    	a[j] = temp;
    	
    	return;
    }
    
    void Print(int * a)
    {
    	int i;
    	for (i = 0; i < N; i ++)
    	   printf("%d ", a[i]);
    	printf("\n");
    	
    	return;
    }
    

    运行结果如下:
    devc++运行结果

    以上就是与大家分享的全部内容啦,如果觉得对你有帮助,不妨点赞、收藏哦,当然如果有什么谬误,还请大家不吝赐教!谢谢观看!

    展开全文
  • 以118°15′49″为例 经度:用公式 =MID(A1,1,3)+...紫色的“5”表示:取从左边数第5位开始2位;——转换分 绿色的“8”表示:取从左边数第8位开始2位;——转换秒 如果是转换纬度数据应相应的变化参数。 ...

    以118°15′49″为例

    经度:用公式 =MID(A1,1,3)+MID(A1,5,2)/60+MID(A1,8,2)/3600 数据放在A列里,这个公式放在B1里,向下填充即可批量转换! 度分秒在A1

    红色的“3”表示:取前三位数字,如果是纬度就改为2;
    紫色的“5”表示:取从左边数第5位开始,取2位;——转换分
    绿色的“8”表示:取从左边数第8位开始,取2位;——转换秒
    如果是转换纬度数据应相应的变化参数。

    展开全文
  • 排序算法

    2021-03-24 15:09:48
    冒泡排序 从左到右,相邻两个依次比较,大的放右边,一轮下来,最大必在右边,二轮,第二大的在右边第二,。。。 选择排序 ...从左边开始,第一第二两个一组归并排序,第三第四两个一组归并排序

    参考地址:

    http://www.guoyaohua.com/sorting.html

    https://blog.csdn.net/csdn_baotai/article/details/80293679

    1. 冒泡排序
      从左到右,相邻两个依次比较,大的放右边,一轮下来,最大数必在右边,二轮,第二大的在右边第二位,。。。
    2. 选择排序
      遍历,找出最小的,跟最左边的换,找出第二小的,跟左边第二位换,。。。
    3. 插入排序
      从左到右依次取数,插入左边,保证左边小,右边大。
    4. 希尔排序
      先分length/2组,每组插入排序,再分成length/2/2组,每组插入排序。。。
    5. 归并排序
      从左边开始,第一第二两个一组归并排序,第三第四两个一组归并排序,第一二三四四个一组归并排序,。。。八个一组归并排序,。。。
    6. 快速排序
      从左边开始取一个数为基准,小的放左边,大的放右边,再从左边开始,直到都成为基准。
    7. 堆排序
      二叉树,大的放父节点,然后取出父节点,就是最大值,依次从大到小取
    8. 计数排序
      按范围分组,放进分组中,再按范围依次列出。
    9. 桶排序
      根据函数均匀分布放进桶,再按桶取出。
    10. 基数排序
      按个位分组,按个位数从小到大取出,再按十位数分组,按十位数从小到大取出,。。。
    展开全文
  • 写一个函数,将此字符串中从第m个字符开始的全部字符复制成为另一个字符串。 76 10.6输入一行文字,找出其中大写字母,小写字母,空格,数字及其他字符各有多少。 77 10.7写一个函数,将一个3×3的矩阵转置。 77 9.8...
  • 直接插入排序

    2020-10-07 22:18:17
    下一个元素比较后实现排序,形成新的数组, 再取第三个元素与该数组比较, 比较时该数组的最后一位开始比较, 若新元素比与其比较的元素小,则将该比较的元素后移以为, 直到新元素比该数组左边找到其应该插入的...
  • 该方法基于二叉树或者堆来实现,首先把数组前k个数字构建一个最大堆,然后从第k+1个数字开始遍历数组,如果遍历到的元素小于堆顶的数字,那么久将换两个数字,重新构造堆,继续遍历,最后剩下的堆就是最小的k个,...
  • 第一参数为ROW时先行后列取值,为COLUMN时先列后行(不分大小写),第三参数开始为引用区域 消除空值消除空值函数。可以选择多行多列,按先行后列之方式返回值.两个参数,一为区域一为序号 颜色求和按背景颜色对区域值...
  • 第一参数为ROW时先行后列取值,为COLUMN时先列后行(不分大小写),第三参数开始为引用区域。 函数名称:消除空值 函数功能与参数:消除空值函数。可以选择多行多列,按先行后列之方式返回值.两个参数,一为区域一为...
  • 第一参数为ROW时先行后列取值,为COLUMN时先列后行(不分大小写),第三参数开始为引用区域。 函数名称:消除空值 函数功能与参数:消除空值函数。可以选择多行多列,按先行后列之方式返回值.两个参数,一为区域一为...
  • 【快捷综合取数】 功能较<快捷取数列>功能更强大,支持同时取6个不同存储格区域(或列)为6个唯一值清单,并在指定的6个不同的生效范围自适应地显示对应的清单。清单的最后6项也为子程序功能,能完成相关操作。且...
  • 【快捷综合取数】 功能较<快捷取数列>功能更强大,支持同时取6个不同存储格区域(或列)为6个唯一值清单,并在指定的6个不同的生效范围自适应地显示对应的清单。清单的最后6项也为子程序功能,能完成相关操作。且...
  • 在这个位域定义中,a占一字节的4,后4填0表示不使用,b从第二字节开始,占用4,c占用4。 2. 由于位域不允许跨两个字节,因此位域的长度不能大于一个字节的长度,也就是说不能超过8二进位。 3. 位域...
  • Excel百宝箱8.0

    2011-06-07 21:32:17
    第一参数为ROW时先行后列取值,为COLUMN时先列后行(不分大小写),第三参数开始为引用区域。 函数名称:消除空值 函数功能与参数:消除空值函数。可以选择多行多列,按先行后列之方式返回值.两个参数,一为区域一为...
  • 精易模块[源码] V5.15

    2015-03-21 22:03:37
    6、新增“类_任务栏”可以显示隐藏任何第三方窗口图标,相当于易中的(不在任务栏显示),带【实例】演示。 7、新增“类_线程池1”中的“等待”方法。 8、修复“编码_Utf8到Ansi“分配内存失败BUG,感谢易友【仁鹰】...
  • EXCEL百宝箱8.0终极版

    2011-11-05 16:48:02
    第一参数为ROW时先行后列取值,为COLUMN时先列后行(不分大小写),第三参数开始为引用区域。 函数名称:消除空值 函数功能与参数:消除空值函数。可以选择多行多列,按先行后列之方式返回值.两个参数,一为区域一为...
  • 数据结构与算法.xmind

    2020-06-19 17:04:23
    外层for循环控制需要排序的趟(1开始因为将0看成了有序数据) 内层while循环加上角标>0的条件查找出要插入的何时位置 退出内层while循环后就找到了合适的位置插入 优化思路 ...
  • javascript入门笔记

    2018-05-15 15:01:07
    赋值符号出现的话,永远都是将右边的值,赋值给左边的变量(右向左运算) 2、常量 1、什么是常量 在程序中,一旦声明好,就不允许被修改的数据 2、声明常量 const 常量名=值; 常量名在命名时采用全大写形式 ...
  • 左边的显示区保持不变,右边动态显示积分和总时间统计信息,其中积分栏目显示当前已经吃下的豆子数目,总时间显示本局游戏从开始到现在经过的时间。 (2) 优化主程序,注意CPU和内存的使用效率。 (3) 考虑一个...
  • 岳维功 ortp-realease.pdf

    2020-12-24 04:00:17
    关」中时间戳的计算问题:年到现在的经过的秒赋值给时间 戳的高位,这个时间的低位通过当前获取的纳秒时间值计算得到。将秒划分为 的次方来衣示,则份了持续的时间大约皮秒。如果当前时间为秒毫秒, 则毫秒为 微妙...

空空如也

空空如也

1 2 3 4
收藏数 76
精华内容 30
关键字:

从左边第三位开始取数