leetcode練習——數組篇(1)(std::ios::sync_with_stdio(false);std::cin.tie(nullptr);)

題號1.?兩數之和:

給定一個整數數組 nums?和一個目標值 target,請你在該數組中找出和為目標值的那?兩個?整數,并返回他們的數組下標。

你可以假設每種輸入只會對應一個答案。但是,你不能重復利用這個數組中同樣的元素。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

才拿到這道題時,第一個反應是遍歷每個元素 x,并查找是否存在一個值與 target?x 相等的目標元素的暴力解法,時間復雜度為O(n2),C++實現如下:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ret;for (int i = 0; i < nums.size(); i++){for(int j = i + 1; j < nums.size(); j++){if(nums[i] == target - nums[j]){ret.push_back(i);ret.push_back(j);return ret;}                }}ret.push_back(-1);ret.push_back(-1);return ret;}
};

?

系統耗時顯示是164ms,?對于每個元素,我們試圖通過遍歷數組的其余部分來尋找它所對應的目標元素,這將耗費?O(n)?的時間。因此時間復雜度為?O(n^2),空間復雜度為O(1)。

?

為了對運行時間復雜度進行優化,我們需要一種更有效的方法來檢查數組中是否存在目標元素。如果存在,我們需要找出它的索引。保持數組中的每個元素與其索引相互對應的最好方法是什么?哈希表。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target){unordered_map<int, int> hm1;for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i];if(hm1.find(complement) != hm1.end()){return vector<int>{hm1.find(complement)->second, i};}hm1[nums[i]] = i;}return vector<int>{-1, -1};}
};

時間立馬縮減到了8ms,性能的提升是立竿見影的,但是看了標準答案,看到有位大神居然將耗時縮減到了4ms,這里附上他的解法:

static const auto io_sync_off = []()
{// turn off syncstd::ios::sync_with_stdio(false);// untie in/out streamsstd::cin.tie(nullptr);return nullptr;
}();class Solution {
public:vector<int> twoSum(vector<int>& nums, int target){map<int, int> hm1;for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i];if(hm1.find(complement) != hm1.end()){return vector<int>{hm1.find(complement)->second, i};}hm1[nums[i]] = i;}return vector<int>{-1, -1};}
};

看完特地查了下開頭的函數,詳細的解釋在下面:https://blog.csdn.net/qq_32320399/article/details/81518476

https://blog.csdn.net/YinJianxiang/article/details/76436089

在ACM里,經常出現數據集超大造成 cin TLE的情況。這時候大部分人(包括原來我也是)認為這是cin的效率不及scanf的錯,甚至還上升到C語言和C++語言的執行效率層面的無聊爭論。其實像上文所說,這只是C++為了兼容而采取的保守措施。我們可以在IO之前將stdio解除綁定,這樣做了之后要注意不要同時混用cout和printf之類

在默認的情況下cin綁定的是cout,每次執行 << 操作符的時候都要調用flush,這樣會增加IO負擔。可以通過tie(0)(0表示NULL)來解除cin與cout的綁定,進一步加快執行效率。


題號4. 尋找兩個有序數組的中位數:

給定兩個大小為 m 和 n 的有序數組?nums1?和?nums2

請你找出這兩個有序數組的中位數,并且要求算法的時間復雜度為?O(log(m + n))。

你可以假設?nums1?和?nums2?不會同時為空。

示例 1:

nums1 = [1, 3]
nums2 = [2]則中位數是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]則中位數是 (2 + 3)/2 = 2.5

我的思路是類似二路歸并排序,但是不需要新的數組來存放兩個數組的數據,也不需要將所有數據全部排序,只需要取到中間兩個數。首先計算出總個數,然后求出中間兩個數的下標 m 和 n ,定義兩個指針,分別從兩個數組的左邊開始向后推進,知道遍歷到第 m 個和第 n 個,求出兩數的平均數并返回。當然這里同樣解除了 IO 的同步用于提升性能。

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{int size = nums1.size() + nums2.size();int m = 0, n = 0;// 判斷中位數是兩數平均值還是單個值if (size % 2 == 1) // 總個數為基數則為中間值{n = size / 2;m = n;}else                // 偶數則為中間倆個數的平均值{n = size / 2;m = n - 1;}double midData = 0;int leftPoint  = 0;int rightPoint = 0;// 獲取中位數for (int i = 0; i <= n; ++i){// 對數組進行判斷是否越界if ( leftPoint >= nums1.size() ) // 即將進行的操作下標將越界{if (midData == 0)midData = ( (double)( nums2[m - leftPoint] + nums2[n - leftPoint] ) ) / 2;elsemidData = ( midData + nums2[n - leftPoint] ) / 2;return midData;}if ( rightPoint >= nums2.size() ) // 即將進行的操作下標將越界{if (midData == 0)midData = ( (double)( nums1[m - rightPoint] + nums1[n - rightPoint] ) ) / 2;elsemidData = ( midData + nums1[n - rightPoint] ) / 2;return midData;}// 向后推進if (nums1[leftPoint] <= nums2[rightPoint]){if (i == m)midData = (double)nums1[leftPoint];if (i == n){midData = ( midData + nums1[leftPoint] ) / 2;return midData;}leftPoint++;} else{if (i == m)midData = (double)nums2[rightPoint];if (i == n){midData = ( midData + nums2[rightPoint] ) / 2;return midData;}rightPoint++;}}return midData;
}

這里出現了一個很奇怪的事情,我的方法在leetcode上顯示的時間耗時是32ms,我采用16ms的方法,提交之后還是顯示的32ms,于是我在自己電腦上寫了測試用例計算耗時:

#include <iostream>
#include <windows.h>
#include <vector>
#include <unordered_map>using namespace std;// 關閉 IO 同步
static const auto io_sync_off = []()
{// turn off syncstd::ios::sync_with_stdio(false);// untie in/out streamsstd::cin.tie(nullptr);return nullptr;
}();double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{int size = 0;if(nums1.size() != 0 || nums2.size() != 0){size = nums1.size() + nums2.size();}else{return false;}int m = 0, n = 0;// 判斷中位數是兩數平均值還是單個值if (size % 2 == 1) // 總個數為基數則為中間值{n = size / 2;m = n;}else                // 偶數則為中間倆個數的平均值{n = size / 2;m = n - 1;}double midData = 0;int leftPoint  = 0;int rightPoint = 0;// 獲取中位數for (int i = 0; i <= n; ++i){// 對數組進行判斷是否越界if ( leftPoint >= nums1.size() ) // 即將進行的操作下標將越界{if (midData == 0)midData = ( (double)( nums2[m - leftPoint] + nums2[n - leftPoint] ) ) / 2;elsemidData = ( midData + nums2[n - leftPoint] ) / 2;return midData;}if ( rightPoint >= nums2.size() ) // 即將進行的操作下標將越界{if (midData == 0)midData = ( (double)( nums1[m - rightPoint] + nums1[n - rightPoint] ) ) / 2;elsemidData = ( midData + nums1[n - rightPoint] ) / 2;return midData;}// 向后推進if (nums1[leftPoint] <= nums2[rightPoint]){if (i == m)midData = (double)nums1[leftPoint];if (i == n){midData = ( midData + nums1[leftPoint] ) / 2;return midData;}leftPoint++;} else{if (i == m)midData = (double)nums2[rightPoint];if (i == n){midData = ( midData + nums2[rightPoint] ) / 2;return midData;}rightPoint++;}}return midData;
}// 性能最優解法
int findKth(vector<int> nums1, vector<int> nums2, int k) 
{if (nums1.empty()) return nums2[k - 1];if (nums2.empty()) return nums1[k - 1];if (k == 1) return min(nums1[0], nums2[0]);int i = min((int)nums1.size(), k / 2), j = min((int)nums2.size(), k / 2);if (nums1[i - 1] > nums2[j - 1]) {return findKth(nums1, vector<int>(nums2.begin() + j, nums2.end()), k - j);} else {return findKth(vector<int>(nums1.begin() + i, nums1.end()), nums2, k - i);}return 0;
}double findMedianSortedArrays2(vector<int>& nums1, vector<int>& nums2) 
{int m = nums1.size(), n = nums2.size();return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0;
}int main() 
{struct timespec startTime,endTime;// 題號 4 測試用例
#if 1clock_gettime(CLOCK_MONOTONIC, &startTime);vector<int> vector1;vector<int> vector2;vector1.push_back(1);vector1.push_back(2);vector2.push_back(4);vector2.push_back(6);clock_gettime(CLOCK_MONOTONIC, &endTime);cout << "pushIn vector time cost :" << endTime.tv_nsec - startTime.tv_nsec << " ns" << endl;// my methodclock_gettime(CLOCK_MONOTONIC, &startTime);for (int i = 0; i < 10; ++i)findMedianSortedArrays(vector1,vector2);clock_gettime(CLOCK_MONOTONIC, &endTime);cout << "my   function time cost :" << endTime.tv_nsec - startTime.tv_nsec << "ns" << endl;// 最佳方法clock_gettime(CLOCK_MONOTONIC, &startTime);for (int i = 0; i < 10; ++i)findMedianSortedArrays2(vector1,vector2);clock_gettime(CLOCK_MONOTONIC, &endTime);cout << "best function time cost :" << endTime.tv_nsec - startTime.tv_nsec << "ns" << endl;
#endifreturn 0;  
}

我的電腦上函數運行10次耗時如圖所示。

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

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

相關文章

intellij idea 中去除 @Autowired 注入對象帶來的紅色下劃線報錯提示

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 PS&#xff1a; 有 2 種方法&#xff0c;第 2 種方法更簡單&#xff0c;在此謝謝好心友人的評論。 方法1&#xff1a; idea中通過Autow…

根據目標選擇減肥方法 少做無用功

不同的美體目標適合的減肥方法也是不同的&#xff0c;有些人想減去大部分體重&#xff0c;而有些人只是想讓身體曲線更柔美&#xff0c;這就要求有相應的減肥方法&#xff0c;對癥下藥&#xff0c;才會讓減肥少做無用功。 目標&#xff1a;我想穿上小一碼的衣服 建議&#x…

Coolite動態加載CheckboxGroup,無法在后臺中獲取

Coolite在后臺動態加載CheckboxGroup&#xff0c;頁面顯示都正常&#xff0c;但是在后臺去獲取選中的checkbox時&#xff0c;使用下方法&#xff1a; ///<summary>///獲取所選權限 ///</summary>///<returns></returns>privatestringGetPermiss…

基于java的數據結構學習——動態數組C++類模板(含拷貝構造,重載常見運算符)

之前實現了java的動態數組&#xff0c;試著寫了個C版的&#xff0c;同樣對時間復雜度振蕩進行了處理。純手打&#xff0c;代碼如下 &#xff1a; // // Created by PC-Saw on 2018/12/19. //#ifndef DATA_STRUCTURE_MYARRAY_H #define DATA_STRUCTURE_MYARRAY_H#include <i…

科目三考試過程詳解

科目三是考駕照的最后一項考試&#xff0c;所以考生在這關都很注意&#xff0c;但是有可能是由于過于緊張都難免會有些失誤&#xff0c;如果沒過的話&#xff0c;那也就意味著您拿照的時間又延長了另外還要交補考費。因此很多學員都想一次性把這項考試通過&#xff0c;那么我們…

圖解 IDEA 中 springboot 項目 MyBatis Generator 逆向生成實體類及 mapper 配置文件

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 一、準備工作&#xff1a; 1. 新建一個 配置文件&#xff1a;generatorConfig.xml 。 <?xml version"1.0" encoding&qu…

關于IIS 7.5 限制連接數與流量限制模塊

網頁中的視頻是用戶喜聞樂見的常見形式之一&#xff0c;并在主要的站點中中以某種形式&#xff08;產品視頻、教程視頻、理財場景、user generated content、消費報告等&#xff09;在更廣泛的應用。 其中的一個挑戰是把視頻加入到站點&#xff0c;雖然這并不花費很多代價。高質…

2014版學車考駕照精華攻略 總有一個你需要!趕緊收藏吧!!

新交規&#xff0c;新駕考&#xff0c;拿下本本&#xff0c;著實不容易。2013的你&#xff0c;是否已經踏上學車征程&#xff0c;為了順利拿到本本而苦于八方搜索&#xff0c;四處奔波&#xff0c;一心只為獲得有所幫助的經驗之談、簡單易懂的學車攻略呢&#xff1f;本著鋤強扶…

mybatis 逆向工程生成的 Example 類的使用

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 一.逆向工程 逆向工程可以針對單表自動生成 mybatis 執行所需要的代碼&#xff08;mapper.java,mapper.xml、po&#xff09;, 根據數據…

牛客假日團隊賽8

牛客假日團隊賽8 A Cell Phone Network 思路&#xff1a;最小支配集AC代碼#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<queue> #include<set> #include<string>…

汽車標志大全 買車必知

簡要介紹&#xff1a;為您提供汽車標志、世界汽車標志大全、各種汽車標志、國產汽車標志大全、汽車標志圖片、汽車標志及名稱、名車標志大全、世界名車排行榜、世界十大名車、世界名車圖片等有關汽車標志、汽車圖片、汽車名字及汽車品牌方面的知識。 歐美汽車標志圖片大全_歐美…

解決: Caused by: java.lang.IllegalStateException: Cannot load driver class: com.mysql.jdbc.Driver

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 1. 報錯&#xff1a; Caused by: java.lang.IllegalStateException: Cannot load driver class: com.mysql.jdbc.Driver 2.但是&…

Python與MySQL連接

import MySQLdb #注意大小寫&#xff01;&#xff01;#建立和數據庫系統的連接conn MySQLdb.connect(hostlocalhost,userroot,passwdsmile,dbtest)#獲取操作游標cursor conn.cursor()#執行SQL,創建一個數據庫.cursor.execute("""create database python"…

科目三靠邊停車技巧要領

正在準備科目三的您&#xff0c;對順利通過考試有信心嗎&#xff1f;今天&#xff0c;小編為大家帶來科目三靠邊停車技巧&#xff0c;通過講解靠邊停車考試要求&#xff0c;讓學員更好地掌握相關技巧&#xff0c;希望能幫到大家。 靠邊停車考試項目中規定&#xff0c;車前保險杠…

解決:Field xxMapper in xx.service.impl.xxServiceImpl required a bean of type ‘xx.mapper.xxMapper‘

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 1. 啟動 springboot 項目報錯&#xff1a; Field userMapper in gentle.service.impl.UserServiceImpl required a bean of type gent…

dojo 九 effects dojo/_base/fx 和 dojo/fx

官方教程&#xff1a;Dojo Effects這里講學習一下dojo如何實現淡入、淡出、滑動等效果。實現這些特殊的效果有兩個包 dojo/_base/fx 和 dojo/fx。dojo/_base/fx 中提供了一些基礎的animation方法&#xff0c;如&#xff1a; animateProperty, anim, fadeIn, and fadeOut.dojo/f…

電子路考容易犯錯的五大細節

正在學車的你&#xff0c;知道在電子路考中哪些是考生常犯的錯誤嗎&#xff1f;下面&#xff0c;小編為大家帶來學車考生參加科目三考試特別容易犯錯的地方&#xff0c;尤其是不按規定使用轉向燈和在超車時不能根據道路交通情況合理選擇行車道或速度這兩項犯錯的人最多。 ●起步…

Linux 查看 MySQL 版本的四種方法

1 在終端下執行 mysql -V 2 在help中查找 mysql --help |grep Distrib 3 在mysql 里查看 select version() 4 在mysql 里查看 status 轉自&#xff1a;https://blog.csdn.net/chengyuc/article/details/77094775

html 基本布局介紹

1、div默認是縱向排列的&#xff0c;例子如下&#xff1a; <div id"wrap"><div id"div1">div1</div><div id"div2">div2</div><div id"div3">div3</div> </div> 2、如果要div橫向排列…

考駕照重點科目的關鍵考試技巧

定點停車停不好關鍵在于方向盤打得太晚&#xff0c;而且剎車沒有控制好&#xff01;剎車和方向應該同步進行&#xff0c;方向盤不要打得太多。上坡停車或者3檔以下停車可以先踩離合器&#xff0c;4-5檔停車必須先剎車減速以后再踩離合器。 上坡定點停車步驟&#xff1a;聽到指令…