狗家电面

我有一个思路 - 前 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;
}

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

xGuo 发表于 2018-1-3 23:15
我有一个思路 - 前 i 个数的和为前 i 个 index 的和

假设index from 1...N, keep 一个 sum of index

好思路！求出的和必定是最小的，所以算法是正确的。

xGuo 发表于 2018-1-3 23:15
我有一个思路 - 前 i 个数的和为前 i 个 index 的和

假设index from 1...N, keep 一个 sum of index

是的！ 根据归纳法，这个 section 之前的已经满足条件了， 那么只需要判断当前最大的为idx + 1就行了

xGuo 发表于 2018-1-3 23:15
我有一个思路 - 前 i 个数的和为前 i 个 index 的和

假设index from 1...N, keep 一个 sum of index

好思路，可能需要补充下逆序的判断。

public int find(int[] nums) {
  if (nums.length==0) return 0;
  int sum = nums.length*(1+nums.length)/2;
  int left = sum;
  for (int i=0;i<nums.length;i++) {
    int isum = (i+2)*(i+1)/2;
    if ((left-=nums[i]) == isum || left+isum == sum) return i;
  }
  return 0;
}

个人觉得O(logN)不太可能，毕竟去check答案是否是正确的也要O(n)，所以会变成O(NlongN)

xGuo 发表于 2018-1-3 23:15
我有一个思路 - 前 i 个数的和为前 i 个 index 的和

假设index from 1...N, keep 一个 sum of index

这个思路看着很好，感谢提供思路，觉得很方便。

贡献个我的思路，很简洁， 大家看对不对：

1. 
   
2. int solve(vector<int> const &nums)
   
3. {
   
4.     int j = 1;
   
5.     for (int i = 0; i < j; j = max(j, nums[i ++]));
   
6.     return j - 1;
   
7. }
   

复制代码

补充内容 (2018-1-4 03:18):
可以略微优化一点速度，提前结束，当然复杂度不变还是O(n)：
int solve(vector<int> const &nums)
{
    int j = 1;
    for (int i = 0; j < nums.size() && i < j; j = max(j, nums[i ++]));
    return j - 1;
}

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

九零 发表于 2018-1-4 03:14
最方便的o(n)思路难道不是保存到当前位置位置的最大值，然后check最大值是否等于index + 1嘛？

当前位置数组的最大值

九零 发表于 2018-1-4 03:14
最方便的o(n)思路难道不是保存到当前位置位置的最大值，然后check最大值是否等于index + 1嘛？

握手，看了ls用sum的, 我以为就我这么想呢。。