得到前i-1個數中比A[i]小的最大值,使用set,然后二分查找

題目

有一個長度為 n 的序列 A,A[i] 表示序列中第 i 個數(1<=i<=n)。她定義序列中第 i 個數的 prev[i] 值 為前 i-1 個數中比 A[i] 小的最大的值,即滿足 1<=j<i 且 A[j]<A[i] 中最大的 A[j],若不存在這樣的數,則 prev[i] 的值為 0。

思路

很顯然,使用雙for循環的復雜度為O(n^2);
偽代碼如下:

for (int i = 1; i < a.size(); i++) {int max = 0;for (int j = 1; j < i; j++) {if(a[j] < a[i] && a[j] > max){max = a[j];}}prev[i] = max;
}

此時可以借助二叉搜索樹來完成這個任務,這樣復雜度就是O(nlogn)了,由于容器set的底層是紅黑樹,我們可以直接使用。
這里介紹一下set的api:lower_bound();
lower_bound() 函數用于在有序區間內查找大于等于目標值的第一個元素。也就是說,使用該函數在指定范圍內查找某個目標值時,最終查找到的不一定是和目標值相等的元素,還可能是比目標值大的元素。
但是返回的迭代器的前一個迭代器則是小于等于目標值的最后一個元素,這一點和前i-1個數中比A[i]小的最大值就不謀而合了。
代碼如下:

set<long>mySet;
for(int i = 0; i < n; i++)
{int tmp;//獲取A[i]cin >> tmp;//基于set數據結構進行二分查找auto iter = mySet.lower_bound(tmp);//前i-1個數中比A[i]小的最大值為(*--iter)if (iter != mySet.begin())	prev[i] = (*--iter);mySet.insert(tmp);
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/376974.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/376974.shtml
英文地址,請注明出處:http://en.pswp.cn/news/376974.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

學習語言貴在堅持

學習語言貴在堅持 轉自&#xff1a;http://zhidao.baidu.com/link?urlr2W_TfnRwipvCDLrhZkATQxdrfghXFpZhkLxqH1oUapLOr8jXW4tScbyOKRLEPVGCx0dUfIr-30n9XV75pWYfK給大家介紹幾本書和別處COPY來的學習C50個觀點 《Thinking In C》&#xff1a;《C編程思想》&#xff1b; 《The…

stl vector 函數_在C ++ STL中使用vector :: begin()和vector :: end()函數打印矢量的所有元素...

stl vector 函數打印向量的所有元素 (Printing all elements of a vector) To print all elements of a vector, we can use two functions 1) vector::begin() and vector::end() functions. 要打印矢量的所有元素&#xff0c;我們可以使用兩個函數&#xff1a;1) vector :: b…

JqueryUI入門

Jquery UI 是一套開源免費的、基于Jquery的插件&#xff0c;在這里記錄下Jquery UI 的初步使用。 第一、下載安裝 下載Jquery,官網&#xff1a;http://jquery.com;  下載Jquery UI&#xff0c;官網&#xff1a;http://jqueryui.com/ Jquery的部署就不說了&#xff0c;說下Jqu…

gp的分布、分區策略(概述)

對于大規模并行處理數據庫來說&#xff0c;一般由單master與多segment組成。 那么數據表的單行會被分配到一個或多個segment上&#xff0c;此時需要想一想分布策略 分布 在gp6中&#xff0c;共有三個策略&#xff1a; 哈希分布 隨機分布 復制分布 哈希分布 就是對分布鍵進行…

[ Java4Android ] Java基本概念

視頻來自&#xff1a;http://www.marschen.com/ 1.什么是環境變量 2.JDK里面有些什么&#xff1f; 3.什么是JRE&#xff1f; 什么是環境變量&#xff1f; 1.環境變量通常是指在操作系統當中&#xff0c;用來指定操作系統運行時需要的一些參數; 2.環境變量通常為一系列的鍵值對&…

_thread_in_vm_Java Thread類的靜態void sleep(long time_in_ms,int time_in_ns)方法,帶示例

_thread_in_vm線程類靜態無效睡眠(long time_in_ms&#xff0c;int time_in_ns) (Thread Class static void sleep(long time_in_ms, int time_in_ns)) This method is available in package java.lang.Thread.sleep(long time_in_ms, int time_in_ns). 軟件包java.lang.Thread…

大規模web服務開發技術(轉)

前段時間趁空把《大規模web服務開發技術》這本書看完了&#xff0c;今天用一下午時間重新翻了一遍&#xff0c;把其中的要點記了下來&#xff0c;權當復習和備忘。由于自己對數據壓縮、全文檢索等還算比較熟&#xff0c;所以筆記內容主要涉及前5章內容&#xff0c;后面的零星記…

IO多路復用的三種機制Select,Poll,Epoll

IO多路復用的本質是通過系統內核緩沖IO數據讓單個進程可以監視多個文件描述符&#xff0c;一旦某個進程描述符就緒(讀/寫就緒)&#xff0c;就能夠通知程序進行相應的讀寫操作。 select poll epoll都是Linux提供的IO復用方式&#xff0c;它們本質上都是同步IO&#xff0c;因為它…

qt中按鈕貼圖

一.QT之QPushButton按鈕貼圖 二.QT之QToolButton按鈕貼圖 一.QT之QPushButton按鈕貼圖具體操作流程 1. Qt Designer中拖入一Tool Button 2. 選擇圖標的圖片放入工程目錄下&#xff0c;如放在Resources內 3. 雙擊工程的Resource Files下的qrc文件&#xff0c;如圖 4. 在彈出的窗…

Ubuntu手動編譯gVim7.3修復終端啟動時與ibus的沖突

個bug伴隨著Ubuntu/ibus的升級苦憋已久&#xff0c;癥狀為終端啟動gvim時卡死&#xff0c;gvim -f可以緩解此問題&#xff0c;但偶爾還是要發作&#xff0c;況且每次末尾托個&也不方便。其實新版gvim已經修復此bug&#xff0c;不過ubuntu安裝包一直沒更新&#xff0c;那我們…

Android Activity類講解(一)

--by CY[kotomifigmail.com] &#xff11;&#xff0e;protected void onCreate(Bundle savedInstanceState) { throw new RuntimeException("Stub!");   } 當創建一個Activity時&#xff0c;系統會自動調用onCreate方法來完成創建工作&#xff0e;該創建工作包括布…

Mysql的undo、redo、bin log分析

目錄關于undo log關于redolog關于binlog一個事務的提交流程undo log :記錄數據被修改之前的樣子 redo log&#xff1a;記錄數據被修改之后的樣子 bin log&#xff1a;記錄整個操作。 關于undo log 關于undo log&#xff1a; 在執行一條涉及數據變更的sql時&#xff0c;在數據…

typedef 字符串_typedef在C中使用字符數組(定義別名來聲明字符串)的示例

typedef 字符串Here, we have to define an alias for a character array with a given number of maximum characters length to read strings? 在這里&#xff0c;我們必須為具有給定最大字符長度數的字符數組定義別名&#xff0c;以讀取字符串 &#xff1f; In the below-…

最小堆實現代碼

參考算法導論、數據結構相關書籍&#xff0c;寫得最小堆實現的源代碼如下&#xff1a; 1 //2 //--最小堆實例3 //4 5 #include <iostream>6 #include <vector>7 #include <string>8 using namespace std;9 10 template<typename Comparable>11 class m…

非常好的在網頁中顯示pdf的方法

今天有一需求&#xff0c;要在網頁中顯示pdf&#xff0c;于是立馬開始搜索解決方案&#xff0c;無意中發現一個非常好的解決方法&#xff0c;詳見http://blogs.adobe.com/pdfdevjunkie/web_designers_guide。 其實就光看這個網站也足夠了&#xff0c;http://www.pdfobject.com/…

Redis字典實現、Hash鍵沖突以及漸進式rehash

本筆記參考《Redis設計與實現》 P24~ 37 目錄Redis字典實現哈希表節點結構哈希表結構字典哈希算法解決hash沖突rehash漸進式hashRedis字典實現 哈希表節點結構 typedef struct dictEntry {// 鍵void *key;// 值 : 可以是一個指針&#xff0c;或者是一個uint64/int64 的整數un…

Java線程類void setContextClassLoader(ClassLoader loader)方法,帶示例

線程類void setContextClassLoader(ClassLoader loader) (Thread Class void setContextClassLoader(ClassLoader loader)) This method is available in package java.lang.Thread.setContextClassLoader(ClassLoader loader). 軟件包java.lang.Thread.setContextClassLoader(…

JPA概要

本文最新版已更新至&#xff1a;http://thinkinside.tk/2012/12/30/JPA.html JPA定義了Java ORM及實體操作API的標準。本文摘錄了JPA的一些關鍵信息以備查閱。 如果有hibernate的基礎&#xff0c;通過本文也可以快速掌握JPA的基本概念及使用。 Table of Contents 1 JPA概述2 實…

如何配置能讓fiddler抓去https的請求?

1、打開fiddler&#xff0c;>>Tools>>Fiddler Options&#xff0c; 打開如圖所示的HTTPS配置項&#xff1a;點擊Export Rppt Certifica to Desktop :桌面上多了一個證書&#xff1a;下面就是將證書導入&#xff1a;點擊開始-運行&#xff0c;輸入&#xff1a;mmc,…

Redis對象的refcount與lru屬性(內存回收、對象共享、空轉時長)

本筆記參考《Redis設計與實現》 P84~P88 內存回收 Redis在對象系統中使用reference counting技術實現了內存回收機制。程序可以通過跟蹤對象的引用計數信息&#xff0c;在適當的時候自動釋放對象并進行內存回收。 typedef struct redisObject {// ...// 引用計數int refcoun…