首页 > 其他分享 >15.72011年42题真题_查找两个序列A和B的中位数

15.72011年42题真题_查找两个序列A和B的中位数

时间:2023-04-12 21:25:27浏览次数:40  
标签:int s2 s1 42 15.72011 m1 d2 题真题 d1

#include <iostream>

int MidSearch(int *A,int *B,int n)
{
    //分别表示序列A和序列B的首位数,末位数和中位数,s是start简写,d是end简写
    int s1=0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    //循环判断结束条件是,两个数组均不断删除最后均只能剩余一个元素
    while (s1!=d1||s2!=d2)
    {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1]==B[m2])
        {
            return A[m1];  //满足条件1
        } else if(A[m1]<B[m2])  //满足条件2
        {
            if((s1 + d1) % 2 == 0){
                //若元素个数为奇数,这里注意数组下标从0开始
                s1=m1;   //舍弃A中间点以前的部分且保留中间点
                d2=m2;   //舍弃B中间点以后的部分且保留中间点
            } else{
                //元素个数为偶数
                s1=m1+1;   //舍弃A中间点及中间点以前部分
                d2=m2;     //舍弃B中间点以后的部分且保留中间点
            }
        } else{
            //满足条件3,下边的操作和上边的条件2是完全对称的
            if ((s1 + d1) % 2==0)
            {
                //若元素个数为奇数
                d1=m1;
                s2=m2;
            } else{
                //元素个数为偶数
                d1=m1;
                s2=m2+1;
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];  //因为题目要的是11,因此我们拿小的那个
}
//2011年42题
int main() {
    int A[] = {11,13,15,17,19,27,29};
    int B[]={2,3,4,5,20,23,27};
    int mid = MidSearch(A,B,7);
    printf("mid=%d\n",mid);
    return 0;
}

 

标签:int,s2,s1,42,15.72011,m1,d2,题真题,d1
From: https://www.cnblogs.com/su-1007/p/17311296.html

相关文章

  • MSBUILD : error MSB3428: Could not load the Visual C++ component "VCBuild.exe".
    完整报错信息:MSBUILD:errorMSB3428:CouldnotloadtheVisualC++component"VCBuild.exe".Tofixthis,1)installthe.NETFramework2.0SDK,2)installMicrosoftVisualStudio2005or3)addthelocationofthecomponenttothesystempathifit......
  • UVa 757 / POJ 1042 / East Central North America 1999 Gone Fishing (枚举&贪心&想
    757-GoneFishingTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=698http://poj.org/problem?id=1042Johnisgoingonafishingtrip.Hehas h hoursavailable( ),andther......
  • day42(2023.4.11)
    1.数据库基本概念2.数据库中,各个概念之间的关系3.数据库分类4.MySQL简介、特点、以及分类 5.下载MySQL   6.MySQL的安装与卸载 7.连接MySQL  8.Navicat工具由于MySQL自带的客户端工具(就是那个黑窗口),有点小小的简陋,也不怎么好看。我们可以......
  • Magical GCD UVA - 1642
     对序列A, 求(j-i+1)*gcd(i,i+1,...j)最大值 G(i)=gcd(G[i-1],a[i]) 即前缀值不升维护1~j-1可能的i 值(logn个) O(n*log^2#include<iostream>#include<map>#include<cmath>#include<algorithm>usingnamespacestd;constintN=......
  • 用 Go 剑指 Offer 42. 连续子数组的最大和
    输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释: 连续子数组 [4,-1,2,1]的和最大,为 6。 提示:1<= arr.length<=10^5-100<=arr[i]<=100......
  • 14.7.2014年41题真题讲解
    function.h////Createdby93757on2023/3/21.//#ifndefINC_1_TREE_FUNCTION_H#defineINC_1_TREE_FUNCTION_H#include<stdio.h>#include<stdlib.h>typedefintBiElemType;typedefstructBiTNode{BiElemTypeweight;//c就是书籍上的data......
  • angular项目启动报Another process, with id 24289, is currently running ngcc.
    在npmbuild时突然停下来,再启动就启不起来了。看报错信息是端口被占用,在任务管理器中也找不到这个端口重启vscode、重启电脑都不好使。。可以通过删除node_modules再重新npminstall解决! ......
  • ZOJ - 2421 Recaman's Sequence(打表水题)
    题目大意:A0=0Am=A(m-1)-m,如果Am小于0或者Am前面已经出现过了,那么Am=A(m-1)+m解题思路:打表水题我用的是map,纪录数是否出现过了#include<cstdio>#include<cstring>#include<map>usingnamespacestd;constintN=500010;typedeflonglongLL;map<LL,int>Ma......
  • 142. 环形链表 II
     解法一:①首先判断是否有环,若无环,则快指针或其下一指针指向空;若有环,则从快慢指针相遇的位置继续出发,直到再次相遇,遍历次数即为环长len。②两指针从头结点重新开始,让其中一指针先出发len步,而后另一指针再出发,相遇节点即为环起点。/***Definitionforsingly-linkedlist.*......
  • 找不到d3dx9_42.dll,无法继续执行代码,的修复方法
    d3dx942.dll文件在是DirectX中的必备文件。,许多游戏或软件需要此文件运行。电脑如果丢失d3dx9_42.dll文件,就会导致软件或游戏无法正常运行打开。下面小编教大家如何解决电脑丢失d3dx9_42.dll的方法在电脑上找到浏览器打开后在顶部输入:dll修复文件.site【按下键盘的回车键打开】进......