济南长清网站建设,网页设计html背景颜色,南京最新消息今天,wordpress备份插件题号1. 两数之和#xff1a;
给定一个整数数组 nums 和一个目标值 target#xff0c;请你在该数组中找出和为目标值的那 两个 整数#xff0c;并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是#xff0c;你不能重复利用这个数组中同样的元素。
示例: …题号1. 两数之和
给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那 两个 整数并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是你不能重复利用这个数组中同样的元素。
示例: 给定 nums [2, 7, 11, 15], target 9 因为 nums[0] nums[1] 2 7 9 所以返回 [0, 1] 才拿到这道题时第一个反应是遍历每个元素 x并查找是否存在一个值与 target−x 相等的目标元素的暴力解法时间复杂度为O(n²)C实现如下
class Solution {
public:vectorint twoSum(vectorint nums, int target) {vectorint 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:vectorint twoSum(vectorint nums, int target){unordered_mapint, int hm1;for (int i 0; i nums.size(); i) {int complement target - nums[i];if(hm1.find(complement) ! hm1.end()){return vectorint{hm1.find(complement)-second, i};}hm1[nums[i]] i;}return vectorint{-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:vectorint twoSum(vectorint nums, int target){mapint, int hm1;for (int i 0; i nums.size(); i) {int complement target - nums[i];if(hm1.find(complement) ! hm1.end()){return vectorint{hm1.find(complement)-second, i};}hm1[nums[i]] i;}return vectorint{-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(vectorint nums1, vectorint 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_mapusing 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(vectorint nums1, vectorint 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(vectorint nums1, vectorint 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, vectorint(nums2.begin() j, nums2.end()), k - j);} else {return findKth(vectorint(nums1.begin() i, nums1.end()), nums2, k - i);}return 0;
}double findMedianSortedArrays2(vectorint nums1, vectorint 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);vectorint vector1;vectorint 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次耗时如图所示。
