狗家电面

问了一道题

给一个数组，n的长度（n >=1），含有所有1 - n的数字，要求得到一个最小的index，满足条件: 如果把数组小于等于i

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

dex为3

注意由于含有所有的1-n的数字，所以数组里是没有重复元素的。

最方便的o(n)思路难道不是保存到当前位置位置的最大值，然后check最大值是否等于index + 1嘛？

楼主们是怎么记住面试的题啊？我面试完了感觉就把题立马忘掉了。

我有一个思路 - 前 i 个数的和为前 i 个 index 的和

假设index from 1...N, keep 一个 sum of index
同时keep sum of nums
当 sum of index == sum of nums, we have the answer

int find(vector<int> nums) {
        if (nums.empty()) return 0;
        int nsum = 0, isum = 0;
        for (int i = 0; i < nums.size(); i++) {
                int iPlusOne = i + 1;
                isum += iPlusOne;
                nsum += nums[i];
                if (isum == nsum) return i;
        }
        return nums.size() - 1;
}

想问问楼主当时是怎么解的？ 感觉只能想到O(n)的解法，不知道能不能用binary search一类的0 0

感觉也可以用binary search吧？logN可以搞定？

shinichi808 发表于 2017-12-31 14:42
想问问楼主当时是怎么解的？ 感觉只能想到O(n)的解法，不知道能不能用binary search一类的0 0

我当时就是用的O(n)的解法~

雪橇犬 发表于 2017-12-31 14:51
感觉也可以用binary search吧？logN可以搞定？

当时我用的O(n)的，binary search不知道行不行~

就这一题？  good luck!!!!!

雪橇犬 发表于 2017-12-31 14:51
感觉也可以用binary search吧？logN可以搞定？

求问binary search的思路？？感谢！

shinichi808 发表于 2018-1-1 06:33
求问binary search的思路？？感谢！

这个binary search不可能吧

首先index = n 的时候i 肯定可以排好序

感觉不可能用binary search啊

考虑最坏的情况， 5 4 3 2 1

怎么用binary search？

感谢分享～～～～～