c********p
发帖数: 1969 | 1 返回的是index，这个不能排序吧？排序顺序就乱了。。。
哪个解法最优？ |
r*******e
发帖数: 7583 | 2 hashtable吧
【在 c********p 的大作中提到】
: 返回的是index，这个不能排序吧？排序顺序就乱了。。。
: 哪个解法最优？
|
k*******t
发帖数: 144 | 3 可以用先用pair(value, index)， 然后sort pair based on value, 这样也是可以的
，就是比较麻烦点 |
c********p
发帖数: 1969 | 4 嗯，我用的就是hashtable。
【在 r*******e 的大作中提到】
: hashtable吧
|
c********p
发帖数: 1969 | 5 这个有想过但不知道怎么实践。
这个pair，是什么操作，什么数据结构？是自己定义一个wrapper class么？
【在 k*******t 的大作中提到】
: 可以用先用pair(value, index)， 然后sort pair based on value, 这样也是可以的
: ，就是比较麻烦点
|
k*******t
发帖数: 144 | 6 如果你用c/c++的话 就定义一个struct，里面有两个variable, 一个value, 一个index.
sort时用vector的自带的sort, 不过要自己定义一个comparator。 |
k*******t
发帖数: 144 | |
r*******e
发帖数: 7583 | 8 c++用stl pair就好了..
index.
【在 k*******t 的大作中提到】
: 如果你用c/c++的话 就定义一个struct，里面有两个variable, 一个value, 一个index.
: sort时用vector的自带的sort, 不过要自己定义一个comparator。
|
s*******s
发帖数: 1031 | 9 我的代码：
struct itemRecord {
int index;
int val;
itemRecord(int i, int v): index(i), val(v) {}
};
bool itemRecordLess(itemRecord i1, itemRecord i2) {
return i1.val < i2.val;
}
class Solution {
public:
vector twoSum(vector &numbers, int target) {
vector result;
int n = numbers.size();
vector numRecords;
for(int i=0; i
numRecords.push_back(itemRecord(i, numbers[i]));
sort(numRecords.begin(), numRecords.end(), itemRecordLess);
for(int i=0; i
int num = target - numRecords[i].val;
int ind = binarySearch(numRecords, i+1, n-1, num);
if(ind > i) {
if(numRecords[i].index > numRecords[ind].
index) {
result.push_back(numRecords[ind].
index+1);
result.push_back(numRecords[i].index
+1);
} else {
result.push_back(numRecords[i].index
+1);
result.push_back(numRecords[ind].
index+1);
}
return result;
}
}
return result;
}
int binarySearch(vector &numbers, int i, int j, int
target) {
while(i <= j) {
int m = (i+j)/2;
if(target == numbers[m].val)
return m;
else if(target > numbers[m].val)
i = m + 1;
else
j = m - 1;
}
return -1;
}
};
【在 c********p 的大作中提到】
: 返回的是index，这个不能排序吧？排序顺序就乱了。。。
: 哪个解法最优？
|
c********p
发帖数: 1969 | 10 我用java，用什么？
【在 r*******e 的大作中提到】
: c++用stl pair就好了..
:
: index.
|
c********p
发帖数: 1969 | 11 其实这个题用最基本的，每个都试一下，就能通过大oj。
但我不甘心啊。。。
【在 s*******s 的大作中提到】
: 我的代码：
: struct itemRecord {
: int index;
: int val;
: itemRecord(int i, int v): index(i), val(v) {}
: };
: bool itemRecordLess(itemRecord i1, itemRecord i2) {
: return i1.val < i2.val;
: }
: class Solution {
|
c******e
发帖数: 26 | |
t***a
发帖数: 416 | 13 用个map吧，key是numbers的value, value是numbers的index
这是我前几天写的
class Solution {
public:
vector twoSum(vector &numbers, int target) {
unordered_map index;
for(int i = 0; i < numbers.size(); i++){
auto position = index.find(target - numbers[i]);
if(position != index.end()) { //hit!
vector result;
result.push_back(position->second + 1);
result.push_back(i + 1);
return result;
}
index[numbers[i]] = i; //build index
}
throw invalid_argument("result not found");
}
};
【在 c********p 的大作中提到】
: 返回的是index，这个不能排序吧？排序顺序就乱了。。。
: 哪个解法最优？
|
c********p
发帖数: 1969 | 14 好的我捧回去读读。。
【在 t***a 的大作中提到】
: 用个map吧，key是numbers的value, value是numbers的index
: 这是我前几天写的
: class Solution {
: public:
: vector twoSum(vector &numbers, int target) {
: unordered_map index;
: for(int i = 0; i < numbers.size(); i++){
: auto position = index.find(target - numbers[i]);
: if(position != index.end()) { //hit!
: vector result;
|
