题解 | #动物牛的数学问题# 二分查找解法

动物牛的数学问题

https://www.nowcoder.com/practice/a732430a93914e3a96a200a45e3a150e

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    struct node{
        int i;
        int num;
        bool operator <(const node& b)const
        {
            return num<b.num;
        }
        node(int index,int n):i(index),num(n)
        {
            
        }
    };
    vector<int> twoSum(vector<int>& nums, int target) {
        // write code here
        //my_nums=nums;
        vector<int> ans;
        for(int i=0;i<nums.size();i++)
        {
            my_nodes.push_back(node(i,nums[i]));
        }
        sort(my_nodes.begin(),my_nodes.end());
        for(int i=0;i<my_nodes.size()-1;i++)
        {
            int res=half_find(my_nodes,i+1, my_nodes.size(), target-my_nodes[i].num);
            if(res!=-1)
            {
                ans.push_back(my_nodes[i].i);
                ans.push_back(my_nodes[res].i);
                return ans;
            }
        }
        return ans;
    }
    
    int half_find(vector<node>& nodes,int l,int r,int target)
    {
        int mid=(l+r)/2;

        if(l>r)
        {
            return -1;
        }
        
        if(nodes[mid].num==target)
        {
            return mid;
        }
        else if(nodes[mid].num>target)
        {
            return half_find(nodes,l, mid-1, target);
        }
        else
        {
            return half_find(nodes,mid+1, r, target);
        }
        return -1;
    }
private:
    vector<node> my_nodes;
};

全部评论

相关推荐

序&nbsp;朋友们,好久不见。&nbsp;笔者在过去消失的五个月里被困在情绪牢笼中过的相当煎熬,一度丢失自己,觉得整个世界都是昏暗的。&nbsp;庆幸的是靠着自己纯硬扛也是走出来了。表达欲再度回归,所以真的很开心还有机会能在再和大家见面。&nbsp;破碎秋招&nbsp;抑郁情绪的引爆点必然是秋招期间遭受的打击了,从去年九月份腾讯转正被告知失败之后就开始疯狂投递简历,每天都在经历:简历挂、一面挂、二面挂、三面挂、HR面挂,每天睁开眼就被无所适从的挫败感包围。&nbsp;秋招的特点是即便流程走到最后一步也不一定会&nbsp;offer,因为还需要进入大池子进行横向对比,俗称泡池子,而这一泡我的大多数面试流程到后面就没了后文,这一度让我感觉非常绝望。我深知自己学历并...
SoNiC_X:我已经工作快2年了,当时高考没考好没去到想去的学校,觉得天要塌了;校招找不到工作,觉得天要塌了;现在工作觉得看不到未来,觉得天要塌了;最近最大的感悟就是:天会一直塌,但是生活也会一直继续下去,还是要调整好自己的心态,不要因为一时的困难把自己困住,要记住完蛋的日子永远在后头
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务