O(n) is slower than O(nlogn)?


  • 0
    S

    the O(nlogn) solution ,beat 89.1%

    O(nlogn)的解法,击败了89.1%的C++代码

     class Solution {
        public:
            vector<int> twoSum(vector<int>& nums, int target) {
                vector<int> result;
                vector<int> copy;
                copy=nums;
                sort(copy.begin(),copy.end());
                auto fir=copy.begin();
                auto sec=--copy.end();
                while(fir<sec&&*fir+*sec!=target)
                {
                    if(*fir+*sec>target)
                        sec--;
                    else
                        fir++;
                }
                auto pos1=nums.begin();
                auto pos2=nums.begin();
                if(*fir!=*sec)
                {
                    pos1=find(nums.begin(),nums.end(),*fir);
                    pos2=find(nums.begin(),nums.end(),*sec);  
                    if(pos1>pos2)
                    {
                        auto temp=pos1;
                        pos1=pos2;
                        pos2=temp;
                    }
                }
                else
                {
                    pos1=find(nums.begin(),nums.end(),*fir);
        			pos2 = find(pos1+1, nums.end(), *sec);
                }
              
                result.push_back(pos1-nums.begin()+1);
                result.push_back(pos2-nums.begin()+1);
                return result;
                
            }
        };
    

    the O(n) solution ,only beat 58%

    O(n)的解法,只击败了58%。

    class Solution {
    public:
    	vector<int> twoSum(vector<int>& nums, int target) {
    		vector<int> result;
    		auto pos1 = nums.begin();
    		auto pos2 = pos1;
    		unordered_map<int, vector<int>::iterator> iht;
    		auto pos = iht.begin();
    		for (auto i = nums.begin(); i != nums.end(); ++i)
    		{
    			pos = iht.find(target - *i);
    			if (pos == iht.end())
    			{
    				iht.insert(pair<int, vector<int>::iterator>(*i, i));   
    			}
    			else
    			{
    				pos2 = i;
    				break;
    			}
    		}
    		pos1 = iht[target-*pos2];
    		result.push_back(pos1 - nums.begin() + 1);
    		result.push_back(pos2 - nums.begin() + 1);
    		return result;
    	}
    };
    

    why? If you know ,please tell me.

    为啥?跪求大神指教


  • 0

    check the complexity of MAP


  • -2
    L

    for loop里有个find, Iht.find 本身就是O(n),所以下面其实是O(n)^2


  • 0
    S

    用的是哈希表,哈希表查找是常数时间,即使不用哈希表,常规的MAP用红黑树实现的,查找也只要logN的时间,不会出现O(n2)


  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

  • 0
    L

    是我疏忽了 ,没细读,万分抱歉


  • 0
    S

    这里用的并不是std::find,而是std::unordered_map::find, 二者不一样。你应该看http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

    leetcode显示问题,下划线显示不出来。


  • 0
    H

    maybe try
    iht.reserve(nums.size());
    before the for loop


  • 1
    L

    How about {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,6} , find 11 ? When the given number set cause collision, worse case liner time O(n) comes. Also refer to "Complexity" session http://www.cplusplus.com/reference/unordered_map/unordered_map/insert/


  • 0
    S

    很简单的问题,测试用例的关系啊,一共15个用例,长度也并不长,O(n)不一定比O(nlogn)花时间少啊,牵扯到系数和每步消耗时间啊。


  • 0
    L

    我写for从两边查,有个用力10000多个元素的数组 说我超时。。。


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.