f*****m
发帖数: 309 | 1 1. 一个array, 求其中那个出现最多次数的属，比如[1,2,3,4,1,2,3,1,6,78,9] 是1
要求constant space and linear time complexity.
2. 3d的图像数据怎么投影到一个视角看到的二位平面会比较好，数据怎么存。
follow up，数据投影到了二维平面后写code吧二维面生成的形状画出来。 | o*******r
发帖数: 73 | 2 题目很有意思，我想了想，第一道题可以先按照bit来二分，复杂度应该是O(32n)。试
着写了
一下代码，不知道有没有bug. 还望高手指教。
public class Solution {
public int find(int[] nums) {
if (nums == null || nums.length == 0) throw new
IllegalArgumentException();
else if (nums.length == 1) return nums[0];
else {
split(nums, 0, nums.length - 1, 0);
int index = 0;
int ret = nums[0];
int cnt = 1;
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[index]) {
count++;
} else {
if (count > cnt) {
ret = nums[index];
cnt = count;
}
index = i;
count = 1;
}
}
if (count > cnt) {
ret = nums[index];
cnt = count;
}
return ret;
}
}
private void split(int[] nums, int left, int right, int pos) {
if (left >= right || pos == 32) return;
int l = left, r = right;
for (int i = left; i <= right; i++) {
while (i < right && (nums[i] & (1 << pos)) != 0) {
int t = nums[right];
nums[right] = nums[i];
nums[i] = t;
right--;
}
while (i > left && (nums[i] & (1 << pos)) == 0) {
int t = nums[left];
nums[left] = nums[i];
nums[i] = t;
left++;
}
}
split(nums, l, left, pos + 1);
split(nums, left + 1, r, pos + 1);
}
}
第二道题我没有图形图像背景，也想了想。不知道对不对，就当抛砖引玉了。我们考虑
2D投射到1D吧，这样简单些。二维的图形有一些key point比如用（x, y）表示，然后
这些key point可以连接成一个mesh, 投影的话最后不要把这些key point投重复了。
然后用向量旋转，记得是乘(cosA, sinA)，然后只留下x或者y坐标。。不知道我说清楚
了没。 | o*******r
发帖数: 73 | | s******d
发帖数: 278 | 4 第二个问题是是用PCA吗？
【在 f*****m 的大作中提到】
: 1. 一个array, 求其中那个出现最多次数的属，比如[1,2,3,4,1,2,3,1,6,78,9] 是1
: 要求constant space and linear time complexity.
: 2. 3d的图像数据怎么投影到一个视角看到的二位平面会比较好，数据怎么存。
: follow up，数据投影到了二维平面后写code吧二维面生成的形状画出来。
| J*********s
发帖数: 29 | 5 第一题不存在解，除非你找的是majority number。
参见 https://en.m.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm | f*****m
发帖数: 309 | 6 日，那面试官为啥要我找constant space 的解？我先秒杀majority I , majority II
，问道这题后没任何思路，说了下hash，面试官问我有没有constant space的方法。没
给答案啊，这是被黑了么？
【在 J*********s 的大作中提到】
: 第一题不存在解，除非你找的是majority number。
: 参见 https://en.m.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm
| l********e
发帖数: 103 | 7 这题是指限制1-9的数字 还是任何数字都可啊？
【在 f*****m 的大作中提到】
: 1. 一个array, 求其中那个出现最多次数的属，比如[1,2,3,4,1,2,3,1,6,78,9] 是1
: 要求constant space and linear time complexity.
: 2. 3d的图像数据怎么投影到一个视角看到的二位平面会比较好，数据怎么存。
: follow up，数据投影到了二维平面后写code吧二维面生成的形状画出来。
|
|
