首页 > 代码库 > leetcode-two sum
leetcode-two sum
之前是通过hash来做,O(n)。这次为了熟悉通用性的解法,通过双指针来做。时间复杂度为O(nlogn)(即sort的复杂度)。
主要是关于sort的用法上不太熟,关于自定义sort规则。
C++ Reference中给的示例代码如下:
1 // sort algorithm example 2 #include <iostream> // std::cout 3 #include <algorithm> // std::sort 4 #include <vector> // std::vector 5 6 bool myfunction (int i,int j) { return (i<j); } 7 8 struct myclass { 9 bool operator() (int i,int j) { return (i<j);}10 } myobject;11 12 int main () {13 int myints[] = {32,71,12,45,26,80,53,33};14 std::vector<int> myvector (myints, myints+8); // 32 71 12 45 26 80 53 3315 16 // using default comparison (operator <):17 std::sort (myvector.begin(), myvector.begin()+4); //(12 32 45 71)26 80 53 3318 19 // using function as comp20 std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)21 22 // using object as comp23 std::sort (myvector.begin(), myvector.end(), myobject); //(12 26 32 33 45 53 71 80)24 25 // print out content:26 std::cout << "myvector contains:";27 for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)28 std::cout << ‘ ‘ << *it;29 std::cout << ‘\n‘;30 31 return 0;32 }
从中可以看到除了写compare函数外,还可以通过重载圆括号()来写函数对象。
一开始是写了个compare函数。
bool compare(const Node &lhs, const Node &rhs){ return lhs.val < rhs.val;
}
发现对于leetcode而言貌似只能提交class Solution内部的部分。而compare函数放在Solution内部就会出错,放在Solution外面就正常。为什么???
然后就通过重载圆括号写了函数对象,顺利通过。
1 class Solution {//two sum O(nlogn) 2 public: 3 struct Node{ 4 int val; 5 int index; 6 Node(int v, int idx) :val(v), index(idx){} 7 }; 8 struct myclass { 9 bool operator() (Node n1, Node n2) { return (n1.val<n2.val); }10 } myobject;11 12 vector<int> twoSum(vector<int> &numbers, int target) {13 vector<Node> a;14 for (int i = 0; i < numbers.size(); i++)15 {16 a.push_back(Node(numbers[i], i + 1));17 }18 sort(a.begin(), a.end(),myobject );19 int i = 0, j = numbers.size() - 1;20 vector<int> res;21 while (i < j)22 {23 int sum = a[i].val + a[j].val;24 if (sum == target)25 {26 int minIndex = min(a[i].index,a[j].index);27 int maxIndex = max(a[i].index, a[j].index);28 res.push_back(minIndex);29 res.push_back(maxIndex);30 break;31 }32 else if (sum < target)33 {34 i++;35 }36 else37 {38 j--;39 }40 }41 return res;42 }43 };
leetcode-two sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。