Google电面 10/1

zhenghao58 发表于 2015-10-3 03:21
那如果是[100, 99, 1, 2], 100要怎么换到num[100]？

我是这么想的，把这些元素一个个push进hashSet，然后从1开始一个个contains()去查找，结果确实应该是O(n)

donnice 发表于 2015-10-3 03:59
我是这么想的，把这些元素一个个push进hashSet，然后从1开始一个个contains()去查找，结果确实应该是O(n)

嗯……我就是这么做的

谢谢楼主分享 也许就onsite了

zhenghao58 发表于 2015-10-3 03:21
那如果是[100, 99, 1, 2], 100要怎么换到num[100]？

[100,99,1,2]就转换为[1,2,100,99]，超出数组范围的不用管，因为和结果无关，这样第一个和下标不符的是num[2]，对应数字是3

坐看云起 发表于 2015-10-3 05:29
[100,99,1,2]就转换为[1,2,100,99]，超出数组范围的不用管，因为和结果无关，这样第一个和下标不符的是nu ...

转换逻辑是怎样的? 如果100超出数组长度的话，就把他放到数组末尾？或者跟数组的最后一个数交换？那99又怎么换到最后的呢？

zhenghao58 发表于 2015-10-3 05:54
转换逻辑是怎样的? 如果100超出数组长度的话，就把他放到数组末尾？或者跟数组的最后一个数交换？那99又 ...

超出数组长度的，就不用管，可能在里面，也可能在末尾。
[100,99,1,2]
100超范围，不管
99超范围，不管
1在范围内，和100交换
2在范围内，和99交换

另外，如果对应位置和自己的值相同，一样不管

第一道不是原题吗?
https://leetcode.com/problems/first-missing-positive/

摸摸lz～～～这是存心要挂你啊～
ps: 第一题就是first missing positive. 遇到超过arrays.length-1的数，你直接不管就好了。

摸摸lz～～～这是存心要挂你啊～
ps: 第一题就是first missing positive. 遇到超过arrays.length-1的数，你直接不管就好了。

又见紫风铃 发表于 2015-10-3 00:04
第二道题不知道是不是这个意思。。。

我觉得如果按楼主写的的话 差不多应该是这个意思 要记录父节点确实不好用BFS