leetcode一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode一道题

leetcode一道题# JobHunting - 待字闺中

m*k2012-11-16 08:11

1 楼

leetcode里这道题有一个test case没有看明白，能请哪位给解释一下么？
input: [1,2,4,3] expect: 4
Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point
at coordinate (i, ai). n vertical lines are drawn such that the two
endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together
with x-axis forms a container, such that the container contains the most
water.
Note: You may not slant the container.

m*k2012-11-16 08:11

2 楼

再请教一道题：
First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
这题不是1-N的范围里缺一个数。我看了测试case，类似[1,2,6,7]是可能出现的。这样
就不能用“只有一个数出现奇数次”那种bit xor的办法来解了。
谁有什么好办法？

b*u2012-11-16 08:11

3 楼

point
together
use 2 and 3, v = min(2,3) * (3-1) =2

【在 m***k 的大作中提到】

: leetcode里这道题有一个test case没有看明白，能请哪位给解释一下么？
: input: [1,2,4,3] expect: 4
: Container With Most Water
: Given n non-negative integers a1, a2, ..., an, where each represents a point
: at coordinate (i, ai). n vertical lines are drawn such that the two
: endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together
: with x-axis forms a container, such that the container contains the most
: water.
: Note: You may not slant the container.

b*u2012-11-16 08:11

4 楼

如果没有重复数字的话可以这么弄：
先用0作pivot，快排，把k个正数选出来 O(n) 时间
选k/2 作pivot，快排，结果少的那一侧缺数，对其继续选中值，快排，直到区间为0，
O(lgn)

【在 m***k 的大作中提到】

: 再请教一道题：
: First Missing Positive
: Given an unsorted integer array, find the first missing positive integer.
: For example,
: Given [1,2,0] return 3,
: and [3,4,-1,1] return 2.
: Your algorithm should run in O(n) time and uses constant space.
: 这题不是1-N的范围里缺一个数。我看了测试case，类似[1,2,6,7]是可能出现的。这样
: 就不能用“只有一个数出现奇数次”那种bit xor的办法来解了。
: 谁有什么好办法？

w*o2012-11-16 08:11

5 楼

这题有one pass（或almost？）的解法：
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if(A == null || A.length == 0)
return 1;

int l = 0, r = A.length - 1;
while(l <= r) {
int x = A[l];
if(x == l + 1) {
l++;
} else if(x < 1 || x > r + 1 || A[x - 1] == x)
A[l] = A[r--];
else {
A[l] = A[x - 1];
A[x - 1] = x;
}
}

return l + 1;
}
每次loop，都有一个element被交换到正确的位置。

【在 m***k 的大作中提到】