m***k
发帖数: 946 | 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***k
发帖数: 946 | 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*****u
发帖数: 648 | 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*****u
发帖数: 648 | 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***o
发帖数: 109 | 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 的大作中提到】
: 再请教一道题：
: 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的办法来解了。
: 谁有什么好办法？
|
|
