|
|---|
|
|
|
|
|
|
p******o
发帖数: 125 | 1 Given a sorted integer array and a number, find all the pairs that sum up to
the number.
这个很简单，但现在多了一个条件
What if the array is sorted by absolute value, for example {1, -2, 4, -9},
find the
answer in O(N).
没想出来，请问答案是什么？ | x****r
发帖数: 99 | 2 这题应该是不能用多空间吧？
我想到一个方法不知道对不对
在原来算法两个指针一头一尾向中间扫描的一点改动
两个数之和 有3种情况，要不然是两个正数，要不然是两个负数， 或者一正一副
那么还是同样的两个指针， 跑三次
第一次两个正数指针， 一头一尾， 无视负数找pair
第二次两个负数指针，一头一尾， 无视正数找pair
（这两种情况由于目标数的情况只用选一个）
第三次
!!!重点观察是：正数是从小到大的，负数是从大到小的，所以，这次不是一头一尾两
个指针，而是两个都从头开始（分别指向第一个正数和第一个负数）
这样如果pair的和小了，就增加正指针，如果大了，就增加负指针， 最后就会找到
请指正，谢谢 ：P | i*****r
发帖数: 265 | 3 还是两个指针就够了，一个指向最小的，就是从右向左扫描负数再从左向右扫描正数，
一个指向最大的，先从右向左扫描正数再从左向右扫描负数。这两个指针和原先的两头
两个指针是一回事吧。 | y*****i
发帖数: 727 | 4 O(n)就简单了。先扫描一遍，分成2个队列，正数和负数。
merge一下形成一个sorted array。然后用老的方法。
所有操作都是O(n). | x******3
发帖数: 245 | 5 没有空间限制的话，这个方法挺好的
【在 y*****i 的大作中提到】
: O(n)就简单了。先扫描一遍，分成2个队列，正数和负数。
: merge一下形成一个sorted array。然后用老的方法。
: 所有操作都是O(n).
| x******3
发帖数: 245 | 6 可以只用两个指针实现
一个指在最后一个正数（相当于尾指针），另一个指在最后一个负数（相当于头指针）
刚开始的时候两个指针都往后移，正数指针知找正数，负数指针只找负数
如果正数指针越过了最小正数，正数指针从最大负数开始往后找负数，
如果负数指针也过了最大负数，负数指针从最小正数开始往后找正数
{1, -2, -4, 9} sum=7
#1 p1=9 p2=-4 p1+p2=5 < 7 move p2
#2 p1=9 p2=-2 p1+p2=7
sum=10
#1 p1=9 p2=-4
#2 p1=9 p2=-2
#3 p1=9 p2=1 done
sum=-6
#1 p1=9 p2=-4
#2 p1=1 p2=-4
#3 p1=-2 p2=-4 done
移动的次数应该<3n
up to
-9},
【在 p******o 的大作中提到】
: Given a sorted integer array and a number, find all the pairs that sum up to
: the number.
: 这个很简单，但现在多了一个条件
: What if the array is sorted by absolute value, for example {1, -2, 4, -9},
: find the
: answer in O(N).
: 没想出来，请问答案是什么？
| z****e
发帖数: 2024 | 7 这个题的老方法是什么方法？我怎么除了hash什么都不会？
还有，听说正整数可以O(n)排序，怎么回事？ | B*******g
发帖数: 1593 | 8 老方法是一低一高两个指针往中间移
counting sort radix sort对正整数可以O(n)
【在 z****e 的大作中提到】
: 这个题的老方法是什么方法？我怎么除了hash什么都不会？
: 还有，听说正整数可以O(n)排序，怎么回事？
|
|
|
|
|
|
|
|
