一維數組最大值的算法-tft每日頭條

一維數組最大值的算法

生活更新时间:2024-07-17 19:19:05

題目描述

給定兩個有序數組，如何在O(log(m n))的時間複雜度下求中位數；

如：[1,4][2,3] -> 2.5

[1,6],[5] -> 2

一維數組最大值的算法（每周一道算法題）1

思路分析

如果沒有時間複雜度要求，借助歸并排序的思路，可以在O(m n)的時間複雜度下求解；

大體邏輯如下：

兩個指針分别指向兩個數組的頭部，然後每次移動元素更小的指針，直到移動到中位數的位置；注意邊界的處理，以及奇偶元素的處理即可；

但這個時間複雜度不滿足題目描述要求；

一維數組最大值的算法（每周一道算法題）2

最佳思路分析

這個問題的前提是有序數組，并且涉及到查找元素，所以很容易聯系到二分查找算法；

假如兩個數組分别為a和b,元素個數分别為m和n；從a的中間元素開始處理，判斷這個中間元素在b中的位置，時間複雜度log(n)；

如果發現這個位置小于中位數的位置，那麼就再取a中位于中間位置和結束位置中間的元素判斷；

如果大于中位數的位置，那麼就取a中起始位置和中間位置中間的元素，再進行判斷；

如果恰好是中位數的位置，則可以直接處理；

這樣時間複雜度為O(log(m n))

如果元素不在a中，那麼隻需要将a，b互換，重複即可；

總的時間複雜度為2 * O(log(m n)) ，按照時間複雜度計算即：O(log(m n))

一維數組最大值的算法（每周一道算法題）3

代碼量比較大，需要源碼的關注并回複“第一周算法”即可；

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部

网友关注

生活怎樣洗白大褂
怎樣洗白大褂?洗米水+橘子皮，保留洗米水或是将橘子皮放入鍋内加水燒煮後，将泛黃的衣服浸泡其中搓洗就可以輕松讓衣服恢複潔白，我來為大家講解一下關于怎樣洗白大褂?跟着小編一起來看一看吧!怎樣洗白大褂洗米水+橘子皮，保留洗米水或是将橘子皮放入鍋内... 2022-07-05
生活細膩什麼意思
細膩什麼意思?細膩是漢語詞語，拼音是xìnì，指細緻光滑，也可用來形容描寫、表演等細緻入微，我來為大家講解一下關于細膩什麼意思?跟着小編一起來看一看吧!細膩什麼意思細膩是漢語詞語，拼音是xìnì，指細緻光滑，也可用來形容描寫、表演等細緻入微... 2022-07-12
生活香蔥雞蛋羹如何做
香蔥雞蛋羹如何做?準備食材：雞蛋、小蔥、蒸魚鼓油、香油，食鹽，我來為大家科普一下關于香蔥雞蛋羹如何做?以下内容希望對你有幫助!香蔥雞蛋羹如何做準備食材：雞蛋、小蔥、蒸魚鼓油、香油，食鹽。雞蛋磕入一個較深的容器内，加入1茶匙食鹽。用手動打蛋器... 2022-06-20
生活阿膠糕适宜人群
阿膠糕适宜人群?主要用于治療氣血兩虛引起的，頭暈眼花，失眠多夢，唇舌色淡，月經量少，氣短無力，精神萎靡不振等症狀，今天小編就來聊一聊關于阿膠糕适宜人群?接下來我們就一起去研究一下吧!阿膠糕适宜人群主要用于治療氣血兩虛引起的，頭暈眼花，失眠多... 2022-07-12
生活 excel如何用文字批量替換數字
在工作中，我們有時候會發現手裡的表格中的一些數字看起來是數字，但是在使用公式進行數學運算時結果卻會出錯。這是因為存在一些文本格式的數字，仔細看會發現文本格式數字所在單元格左上角有個綠色小三角，這是表示這些數字是文本格式的。如下圖：箭頭所指為... 2022-11-16
生活新年的詩短句
新年感懷哲理古詩六首賞讀：新年一故成故人，年年月月但如春又是農曆新年到。自漢朝以一月首日為新年，農曆紀年延綿了2000多年，曾經是中國人重要的紀年方式，彼時，并無現在通行的公曆對照，農曆年裡，記錄着2000多年厚重的曆史進程，人們的生老病死... 2022-11-06
生活 word文檔怎麼分頁
word文檔怎麼分頁?首先，打開Word文檔，将光标定位到需要分頁的位置，下面我們就來說一說關于word文檔怎麼分頁?我們一起去了解并探讨一下這個問題吧!word文檔怎麼分頁首先，打開Word文檔，将光标定位到需要分頁的位置。光标定位到需要... 2022-06-07
生活尚義縣隋珠草莓特供冬奧會
尚義縣隋珠草莓特供冬奧會?“我們這裡的草莓是國内唯一一家特供北京2022年冬奧會的!”2月9日上午，在衆多媒體記者面前，張家口市尚義縣紅土梁鎮草莓園的負責人掩飾不住自己的興奮，一再邀請在場的記者走進草莓大棚品嘗，我來為大家科普一下關于尚義縣... 2022-12-09
生活美國國花寓意是什麼
美國國花寓意是什麼?美國的國花是玫瑰花，象征着美麗、芬芳、熱忱和愛情，是愛情、和平、友誼、勇氣和獻身精神的化身，現在小編就來說說關于美國國花寓意是什麼?下面内容希望能幫助到你，我們來一起看看吧!美國國花寓意是什麼美國的國花是玫瑰花，象征着美... 2022-06-07
生活怎樣做鳥巢方便面呢
怎樣做鳥巢方便面呢?主料;方便面50克、雞蛋1個、鹽少許、蔥花适量、黑胡椒碎少許，我來為大家科普一下關于怎樣做鳥巢方便面呢?下面希望有你要的答案，我們一起來看看吧!怎樣做鳥巢方便面呢主料;方便面50克、雞蛋1個、鹽少許、蔥花适量、黑胡椒碎少... 2022-07-16
生活安徒生童話中最著名的童話
小時候接觸到的童話故事，除了格林童話就是安徒生童話，實際上，歐洲是童話故事興盛之地，特别是文藝複興的起源地意大利，更是承載了很多生動有趣的童話故事。意大利童話作品代表文學作家卡爾維諾，他的代表作不局限于童話故事，畢業于文學系的他在長篇小說創... 2022-10-26
生活減脂肪快的方法
減脂肪快的方法?注意控制日常熱量的攝入：說到如何快速減脂肪這個問題，其實減肥不可能一蹴而就，因此在減脂這個問題上也沒有速成的方法，身體肥胖的人群一定要從日常的方方面面去入手，做好相關的應對工作首先，在日常飲食上，一定要注意控制熱量的攝入，注... 2022-06-13
生活烏迪爾的最強出裝順序
烏迪爾在重做之初表現并不佳，不過随着召喚師們的不斷摸索，終于将其打法思路穩定了下來。目前看來法坦主鳳流和穿甲主虎流是烏迪爾兩大主流玩法，今天就為大家簡單介紹一下這兩種流派的思路。法坦主鳳流法坦主鳳流已經一個比較成熟的打法了，目前在韓服表現極... 2022-11-14
生活質量的國際單位都有什麼
質量的國際單位都有什麼?質量的國際單位有千克、毫克、克、噸，現在小編就來說說關于質量的國際單位都有什麼?下面内容希望能幫助到你，我們來一起看看吧!質量的國際單位都有什麼質量的國際單位有千克、毫克、克、噸。國際單位是國際計量大會采納和推薦的一... 2022-06-28
生活中級會計師報考條件及資料
中級會計師報考條件及資料?報考中級職稱資格具備以下條件之一：，我來為大家科普一下關于中級會計師報考條件及資料?下面希望有你要的答案，我們一起來看看吧!中級會計師報考條件及資料報考中級職稱資格具備以下條件之一：（1）大專畢業，從事會計工作滿五... 2022-11-03
生活芝麻餅的做法大全家常菜
做了些蔬菜餅，吃起來味道獨特，非常好吃。是用芝麻菜做的，芝麻菜也叫做東北臭菜，因為含有芥子油，所以越吃味道越重，一般用來做蔬菜沙拉吃，我今天用它做了蔬菜餅，也很棒。【芝麻菜蔬菜餅】配料:芝麻菜500G，蘿蔔1個，面粉2碗，姜粉，鹽，洋蔥半... 2022-11-03
生活水光配比
水光配比?水光針是根據皮膚的需求來搭配，讓我們的面部看起來更飽滿更年輕簡單來說，就是缺什麼補什麼，水分足了，營養夠了，當然你就看起來比别人更年輕漂亮了水光補水搭配的萬能公式，它來咯基礎補水搭配方案：基礎水光（潤月雅水光）、動能素（絲麗516... 2023-04-03
生活推動改革開放的終極力量是什麼
推動改革開放的終極力量是什麼?劉德中中國社會科學院馬克思主義研究院副研究員、博士，下面我們就來聊聊關于推動改革開放的終極力量是什麼?接下來我們就一起去了解一下吧!推動改革開放的終極力量是什麼劉德中中國社會科學院馬克思主義研究院副研究員、博士... 2022-11-07
生活天面烏龜怎樣過冬
天面烏龜怎樣過冬?烏龜利用冬眠的方式來過冬烏龜在15℃以下開始進入冬眠，當水溫升至16℃以上時開始攝食烏龜的抗寒性還可以，一般隻要水溫不低于4℃就能安全越冬，今天小編就來說說關于天面烏龜怎樣過冬?下面更多詳細答案一起來看看吧!天面烏龜怎樣過... 2022-05-31
生活淘寶等級
淘寶等級?打開淘寶進行登錄操作後，點擊左上角個人的用戶名，我來為大家科普一下關于淘寶等級?下面希望有你要的答案，我們一起來看看吧!淘寶等級打開淘寶進行登錄操作後，點擊左上角個人的用戶名。點擊左側欄裡的“評價管理”選項。在打開的界面中就能看到... 2022-06-08
生活瑞士峰遊玩
瑞士峰遊玩?來到瑞士旅行，不能錯過的阿爾卑斯山山脈的少女峰我拉着行李箱一個人從盧塞恩坐黃金列車抵達因特拉肯，為了坐火車登上歐洲的屋脊——少女峰，并體驗齒輪火車盡管天氣非常冷，但我還是充滿期待少女峰海拔4158米，位于瑞士伯爾尼高地，是阿爾卑... 2022-10-19
生活猴子的符文
猴子的符文?四級符文(替代)紅色符文：懲戒，今天小編就來說說關于猴子的符文?下面更多詳細答案一起來看看吧!猴子的符文四級符文(替代)紅色符文：懲戒綠色符文：野性藍色符文：急救藍色獸痕：最大生命+600/暴擊率+5%綠色鷹眼：物理攻擊+9/物... 2022-08-23
生活銷售怎麼去介紹一汽大衆的探歌
一汽-大衆首款SUV車型——探歌已于3月23日的大衆品牌日活動上正式亮相，該車将由一汽-大衆華南基地投産并于7月正式上市。網通社從一汽-大衆官方獲悉：6月22日，一汽-大衆華南基地将正式建成。屆時，一汽-大衆華南基地将生産包括高爾夫家族、探... 2022-11-17
生活每年死于打呼噜的人數
3月5日，天津消防官方抖音賬号直播了探訪消防“新兵連”的一天到了午睡的時間消防員們都回到了各自的床位上進行午休沒過多久直播中就傳來了此起彼伏的呼噜聲觀看人數卻有增無減直播間内超500萬人在線圍觀了消防員“打呼噜”評論區更是讨論的熱火朝天“5... 2022-11-02
生活羅山大腸做法和配方
羅山大腸做法和配方?豬大腸(800克)，海帶(200克)，老抽(适量)，大茴香(适量)，三奈(适量)，丁香(适量)，生姜(适量)，白糖(适量)，白芷(适量)，我來為大家科普一下關于羅山大腸做法和配方?以下内容希望對你有幫助!羅山大腸做法和配... 2022-06-25
生活關于環保資料
關于環保資料?環保專業資料按專業技術可以分為生态環保資料、廢水處理資料、廢氣處理資料、噪聲處理資料、固廢處理資料、環境影響評價資料、清潔生産資料；按用戶需求可分為環保法律法規資料、環保标準規範資料、環保考試資料；信息提供可分為環保設備廠商資... 2022-06-09
生活海蚌介紹
海蚌介紹?漳港海蚌，福建省福州市長樂區特産，中國地理标志保護産品，今天小編就來說說關于海蚌介紹?下面更多詳細答案一起來看看吧!海蚌介紹漳港海蚌，福建省福州市長樂區特産，中國地理标志保護産品。早在明朝時期，漳港海蚌就已成為宮廷貢品。漳港海蚌特... 2022-06-08
生活草莓怎麼保存時間長
草莓怎麼保存時間長?保存草莓不宜放在溫度高的地方，草莓适宜在10度以下的陰涼處保存，溫度過高會使草莓容易腐爛變質草莓含有水分很高，草莓失水以後就會幹縮壞掉我們可以找一個密封袋把草莓裝進裡面去，然後把袋口密封好，然後放在冰箱裡面冷藏這樣可以保... 2022-07-18
生活有澳門衛視嗎
是的，澳門也有電視台。澳門電視台俗稱澳廣視（TDM）主要分為中文頻道跟葡語頻道兩種。葡語頻道裡的節目都是葡語，有人會問了澳門人也不是很多人會說葡語啊為什麼還有個葡語頻道呢直接改為中文頻道不就行了？這麼說就錯啦，澳門還有很多土生葡人的他們很多... 2022-12-16
生活我飛向遠方擋不住憂傷
我從崖邊跌落落入星空遼闊當年，謝春花憑借這首民謠《我從崖邊跌落》，獲得網易雲10w熱評數，無數人分享愛而不得的寂寞歡喜。“我從崖邊跌落，落入星空遼闊”每當讀到這句歌詞，常使我幻想：在遼闊懸崖邊、繁盛星空下，雙手張開，躺在草地上，仰望整個宇宙... 2022-11-25

tft每日頭條

> 生活

> 一維數組最大值的算法

一維數組最大值的算法

相关生活资讯推荐

热门生活资讯推荐

网友关注