w***y
发帖数: 6251 | 1 这种题怎么做啊? 如果是sorted的, 找一个我知道可以用binary search的法子
如果找更多个, 即使是sorted的, 我也想不出什么法子了......... | s******n
发帖数: 240 | 2 求和，平方求和，立方求和，...
有k个等式，就可以解出来
http://math2.org/math/expansion/power.htm
【在 w***y 的大作中提到】
: 这种题怎么做啊? 如果是sorted的, 找一个我知道可以用binary search的法子
: 如果找更多个, 即使是sorted的, 我也想不出什么法子了.........
| w****o
发帖数: 2260 | 3 能不能把这个问题给个确切的描述？
我觉得有可能是两种情形：
1. 给个数组，数组大小是N,里面的数都介入 1和N,丢了k个数，没有丢的数可能有重复
，因为数组大小还是N.
2. 给个数组，数组大小是N-k,里面的数都介入 1和N,丢了k个数,没有丢的数没有重复。
到底面试的时候被问到的是哪种情形？应该解答也是不一样的吧？！
【在 w***y 的大作中提到】
: 这种题怎么做啊? 如果是sorted的, 找一个我知道可以用binary search的法子
: 如果找更多个, 即使是sorted的, 我也想不出什么法子了.........
| i*********7
发帖数: 348 | 4 能用额外buffer的话，就建hashtable。其实用Bitmap就够了。。。 | w****o
发帖数: 2260 | 5 能说说我上面提到的是哪种情形？
谢谢！
【在 i*********7 的大作中提到】
: 能用额外buffer的话，就建hashtable。其实用Bitmap就够了。。。
| w***y
发帖数: 6251 | 6 我看到的题目是2, 没有重复
复。
【在 w****o 的大作中提到】
: 能不能把这个问题给个确切的描述？
: 我觉得有可能是两种情形：
: 1. 给个数组，数组大小是N,里面的数都介入 1和N,丢了k个数，没有丢的数可能有重复
: ，因为数组大小还是N.
: 2. 给个数组，数组大小是N-k,里面的数都介入 1和N,丢了k个数,没有丢的数没有重复。
: 到底面试的时候被问到的是哪种情形？应该解答也是不一样的吧？！
| w***y
发帖数: 6251 | 7 能不能给一个讲解bit array的link?
我看了wiki 还是不知道怎么实现 http://en.wikipedia.org/wiki/Bit_array
譬如说现在的这个N-k个数, 怎么转化成一个bit array呢?
【在 i*********7 的大作中提到】
: 能用额外buffer的话，就建hashtable。其实用Bitmap就够了。。。
| p*****2
发帖数: 21240 | 8
就是一个bit代表一个数字，省点内存。
【在 w***y 的大作中提到】
: 能不能给一个讲解bit array的link?
: 我看了wiki 还是不知道怎么实现 http://en.wikipedia.org/wiki/Bit_array
: 譬如说现在的这个N-k个数, 怎么转化成一个bit array呢?
| i*********7
发帖数: 348 | | X*K
发帖数: 87 | 10 根据前面的提示写了一个
void missingK(int a[], int n, int k) {
int * bitmap = new int[n / sizeof(int) + 1];
for (int i = 0; i < n - k; ++i) {
int number = a[i];
int index = number / sizeof(int);
int offset = number - number / sizeof(int) * sizeof(int);
bitmap[index] |= 1 << offset;
}
for (int i = 1; i <= n; ++i) {
int index = i / sizeof(int);
int offset = i - i / sizeof(int) * sizeof(int);
if ((bitmap[index] & 1 << offset) == 0) {
cout << "missing: " << i << endl;
}
}
} | f*******t
发帖数: 7549 | 11 #include
#include
bool isSet(char *bitarray, int num)
{
int index = num / 8;
int offset = num % 8;
return bitarray[index] & (char)(1 << offset);
}
void set(char *bitarray, int num)
{
int index = num / 8;
int offset = num % 8;
bitarray[index] |= (char)(1 << offset);
}
void printMissingNum(int *array, int arraysize, int N)
{
int bitarraysize = (N + 7) / 8;
char *bitarray = (char*)calloc(bitarraysize, 1);
for(int i = 0; i < arraysize; ++i) {
set(bitarray, array[i]);
}
for(int i = 0; i < N; ++i) {
if(!isSet(bitarray, i)) {
printf("%d ", i);
}
}
free(bitarray);
printf("\n");
}
int main()
{
int array[] = {1, 2, 3, 5, 6};
int N = 10;
printMissingNum(array, sizeof(array) / sizeof(int), N);
return 0;
} |
|
