问一道G家热题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道G家热题

问一道G家热题# JobHunting - 待字闺中

b*i2014-12-26 08:12

1 楼

考古了半天，没有发现什么好的解法，望大牛指教
给定一个数字数组 ,其中每个元素是从末端数小于原数组中该元素的个数。求原数组。
原数组中元素是从1到n。Example:
原数组4, 1, 3, 2
Count array 3, 0, 1, 0
考古发现这个帖子里面有些讨论，但不是很懂：
http://www.weiming.info/zhuti/JobHunting/31903469/
另外最近G家也考了这一题：
给一个数组a[n]，
令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)
目测可能方法差不多。
谢谢！

k*42014-12-26 08:12

2 楼

merge sort变种

【在 b******i 的大作中提到】

: 考古了半天，没有发现什么好的解法，望大牛指教
: 给定一个数字数组 ,其中每个元素是从末端数小于原数组中该元素的个数。求原数组。
: 原数组中元素是从1到n。Example:
: 原数组4, 1, 3, 2
: Count array 3, 0, 1, 0
: 考古发现这个帖子里面有些讨论，但不是很懂：
: http://www.weiming.info/zhuti/JobHunting/31903469/
: 另外最近G家也考了这一题：
: 给一个数组a[n]，
: 令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)

b*i2014-12-26 08:12

3 楼

具体说说，怎么mergesort法？

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

: merge sort变种

s*32014-12-26 08:12

4 楼

merge sort 只是用于计算总的逆序数，对于单个的逆序数的话，时间复杂度应该还是n
^2

k*42014-12-26 08:12

5 楼

还没测试过，如有bug请指正
struct idxAndCount
{
int idx;
int count;
idxAndCount(int i): idx(i), count(0) {};
};
void mergeSort(const vector&A, vector &C, int start, int
end)
{
if (start>=end)
return;
int mid = start + (end-start)/2;
mergeSort(A, C, start, mid);
mergeSort(A, C, mid+1, end);
vector temp;
int i=start, j=mid+1;
while (i<=mid && j<=end)
{
if (A[C[i].idx] <= A[C[j].idx]
{
C[i].count += C[j].count;
C[i].count += (A[C[i].idx] != A[C[j].idx);
temp.push_back(C[i++]);
}
else
temp.push_back(C[j++]);
}
while (i<=mid)
temp.push_back(C[i++]);
while (j<=end)
temp.push_back(C[j++]);
for (int i=start; i<=end; i++)
C[i] = temp[i-start];
return;
}
vector countBigger(const vector &A)
{
if (A.size() == 0)
{
vector retv;
return retv;
}
vector C;
for (int i=0; i{
idxAndCount t(i,0);
C.push_back(t);
}
mergeSort(A,C, 0, A.size()-1);
vector retv(A.size(), 0);
for(int i=0; iretv[C[i].idx] = C[i].count;
return retv;
}

k*42014-12-26 08:12

6 楼

看成要返回每个s[i], 上面的程序修改下，countBigger中返回retv中的最大值就可以
了。

h*r2014-12-26 08:12

7 楼

考古题能不能这么做：
建一个class Node存count array的index和value
比如楼主的例子：
Node(idx, value)
(0, 3), (1, 0), (2, 1), (3, 0)
然后对于这些node排序，按照value拍，然后value一样时候按照index排
排序后：
(1, 0), (3, 0), (2, 1), (0, 3)
然后这些node在原数组就分别对应1到n
idx = 1: 1
idx = 3: 2
idx = 2: 3
idx = 0: 4

考古了半天，没有发现什么好的解法，望大牛指教
给定一个数字数组 ,其中每个元素是从末端数小于原数组中该元素的个数。求原数组。
原数组中元素是从1到n。Example:
原数组4, 1, 3, 2
Count array 3, 0, 1, 0
考古发现这个帖子里面有些讨论，但不是很懂：
http://www.weiming.info/zhuti/JobHunting/31903469/
另外最近G家也考了这一题：
给一个数组a[n]，
令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)
目测可能方法差不多。
谢谢！

【在 b******i 的大作中提到】

o*c2014-12-26 08:12

8 楼

明显不对，ex: 3 5 1 4 2
应该是使用点树，线段树或树状数组做才能保证O(nlogn)的复杂度。

【在 h*********r 的大作中提到】

: 考古题能不能这么做：
: 建一个class Node存count array的index和value
: 比如楼主的例子：
: Node(idx, value)
: (0, 3), (1, 0), (2, 1), (3, 0)
: 然后对于这些node排序，按照value拍，然后value一样时候按照index排
: 排序后：
: (1, 0), (3, 0), (2, 1), (0, 3)
: 然后这些node在原数组就分别对应1到n
: idx = 1: 1

h*r2014-12-26 08:12

9 楼

多谢指正
不过现在new grad都要考线段树了？

【在 o***c 的大作中提到】

: 明显不对，ex: 3 5 1 4 2
: 应该是使用点树，线段树或树状数组做才能保证O(nlogn)的复杂度。

o*c2014-12-26 08:12

10 楼

我同学两周前onsite被考到了，不过此题线段树写起来也方便。
#define Maxn 10000
int val[1010];
class Segment_Tree {
private:
struct Node {
int left,right,cover;
};
Node Tree[Maxn];
int Number, c, d;
public:
void build(int Now, int a,int b) {
Tree[Now].left=a;
Tree[Now].right=b;
if(b-a>=1) {
int mid=(a+b)>>1;
Tree[Now].left=a;
build(2*Now+1 , a,mid);
Tree[Now].right=b;
build(2*Now+2,mid+1, b);
Tree[Now].cover = Tree[2*Now+1].cover + Tree[2*Now+2].cover;
}
else Tree[Now].cover = 1;
}
void del(int Num, int x) {
if(Tree[Num].left<=x && Tree[Num].right>=x) {
Tree[Num].cover--;
if(Tree[Num].leftdel(2*Num+1, x);
del(2*Num+2, x);
}
}
}
int Count(int Num, int x) {
if(Tree[Num].right == Tree[Num].left) return Tree[Num].left;
else {
if(Tree[2*Num+1].cover>=x)
return Count(2*Num+1, x);
else
return Count(2*Num+2, x-Tree[2*Num+1].cover);
}
}
};
int main() {
int n;
int a, b;
Segment_Tree s;
cin >> n ;
for(int i = 0;icin >> val[i];
}
s.build(0, 0, n-1);
for(int i=0;iint x = s.Count(0,val[i]+1);
cout << x + 1 << endl;
s.del(0, x);
}
return 0;
}

【在 h*********r 的大作中提到】

: 多谢指正
: 不过现在new grad都要考线段树了？

b*i2014-12-26 08:12

11 楼

感谢，竟然要用线段树。。奈何我听都没听过这个东西，弱爆了
我来研究下你的code

【在 o***c 的大作中提到】

: 我同学两周前onsite被考到了，不过此题线段树写起来也方便。
: #define Maxn 10000
: int val[1010];
: class Segment_Tree {
: private:
: struct Node {
: int left,right,cover;
: };
: Node Tree[Maxn];
: int Number, c, d;

x*92014-12-26 08:12

12 楼

做了一下
>> 给定一个数字数组 ,其中每个元素是从末端数小于原数组中该元素的个数。求原数
组。
Time complexity: O(n * logn) // quick-sort + traverse
Memo complexity: O(n)
>> 令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)
Time complexity: O(n * logn) // Manipulate the Binary Indexed Tree
Memo compleixty: O(n)
#include
#include
#include
#include
#include
#include
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
const int SIZE = 1024;
// @brief Binary Indexed Tree
class Bitree {
public:
// @brief clear all data
void clear() {
memset(_tree, 0, sizeof(_tree));
}
// @brief array[pos] += value
int add(int value, int pos) {
if (pos <= 0) {
return -1;
}
while (pos < SIZE) {
_tree[pos] += value;
pos += lowbit(pos);
}
return 0;
}
// @brief sum(array[st]...array[end])
int sum(int st, int end) {
return sum(end) - sum(st - 1);
}
private:
// @brief sum(array[1]...array[pos])
int sum(int pos) {
int res = 0;
while (pos > 0) {
res += _tree[pos];
pos -= lowbit(pos);
}
return res;
}
private:
inline static int lowbit(int x) {
return (x) & (-x);
}
private:
int _tree[SIZE];
};
class CountArrayInterface {
public:
virtual vector get_count_array(const vector& ivec) = 0;
};
class CountArraySlow: public CountArrayInterface {
public:
virtual vector get_count_array(const vector& ivec) {
int n = ivec.size();
vector res;
res.resize(n);
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = i + 1; j < n; j++) {
if (ivec[j] < ivec[i]) {
cnt++;
}
}
res[i] = cnt;
}
return res;
}
};
class CountArrayWithBIT: public CountArrayInterface {
public:
virtual vector get_count_array(const vector& ivec) {
int n = ivec.size();
vector vec;
vector counter;
vec.resize(n);
counter.resize(n);
for (int i = 0; i < n; i++) {
vec[ivec[i] - 1] = i;
}
_bit.clear();
for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
int pos = *iter;
counter[pos] = _bit.sum(pos + 1, n);
_bit.add(1, pos);
}
return counter;
}
private:
Bitree _bit;
};
class RecoverArray {
public:
vector recover_array(const vector& counter) {
int n = counter.size();
vector > vec;
vector res;
vec.resize(n);
res.resize(n);
for (int i = 0; i < n; i++) {
vec[i] = {counter[i], i};
}
sort(vec.begin(), vec.end());
for (int i = 0; i < n; i++) {
int pos = vec[i].second;
res[pos] = i + 1;
}
return res;
}
};
int main() {
vector vec = {4, 1, 3, 2};
CountArraySlow counter1;
CountArrayWithBIT counter2;
vector counter_array1 = counter1.get_count_array(vec);
vector counter_array2 = counter2.get_count_array(vec);
for (auto i: counter_array1) {
printf("%d ", i);
}
puts("");

for (auto i: counter_array2) {
printf("%d ", i);
}
puts("");

for (auto i: vec) {
printf("%d ", i);
}
puts("");

RecoverArray ra;
vector recovered_array = ra.recover_array(counter_array1);
for (auto i: recovered_array) {
printf("%d ", i);
}
puts("");

return 0;
};

p*n2014-12-26 08:12

13 楼

这个变种是用原数组求 count array 用merge sort做可以。
但反方向，用count array 求原来数组 O(nlogn)比较麻烦，应该分好几步，有一步是
建立一个balanced BST,每个node存储它left subtree的node的个数。

【在 b******i 的大作中提到】

b*i2014-12-26 08:12

14 楼

请问变种你说的mergesort具体是怎么做来着？不用线段树吗

【在 p********n 的大作中提到】

:
: 这个变种是用原数组求 count array 用merge sort做可以。
: 但反方向，用count array 求原来数组 O(nlogn)比较麻烦，应该分好几步，有一步是
: 建立一个balanced BST,每个node存储它left subtree的node的个数。

m*k2014-12-26 08:12

15 楼

可否分别pseudocode讲讲思路先？多谢多谢！

【在 x*******9 的大作中提到】

: 做了一下
: >> 给定一个数字数组 ,其中每个元素是从末端数小于原数组中该元素的个数。求原数
: 组。
: Time complexity: O(n * logn) // quick-sort + traverse
: Memo complexity: O(n)
: >> 令s[i]为a[i+1..n-1]中比a[i]大的数的数量。求最大的s[i]。要求O(nlogn)
: Time complexity: O(n * logn) // Manipulate the Binary Indexed Tree
: Memo compleixty: O(n)
: #include
: #include

l*02014-12-26 08:12

16 楼

其实这就是一个简单的二叉树插入问题
class TreeNode {
int val;
int offset;
int smaller;
TreeNode left, right;
int leftSize;
TreeNode(int offset, int val) {this.offset = offset; this.val = val; }
}
public class CountingTree {
private TreeNode root;

TreeNode[] buffer;
public CountingTree(int size) {
buffer = new TreeNode[size];
}

public void insert(int offset, int val) {
TreeNode node = new TreeNode(offset, val);

if(root == null) root = node;
else insert(root, node);

buffer[offset] = node;
}

private void insert(TreeNode root, TreeNode node) {
if(node.val <= root.val) {
root.leftSize ++;
if(root.left == null) root.left = node;
else insert(root.left, node);
} else if(node.val > root.val) {
node.smaller += root.leftSize + 1;

if(root.right == null) root.right = node;
else insert(root.right, node);
}
}

private int getSmallerCount(int offset) {
return buffer[offset].smaller;
}
}

l*02014-12-26 08:12

17 楼

赞！

【在 h*********r 的大作中提到】

x*72014-12-26 08:12

18 楼

Count array 就是一个rank
表示当前数字在还存在的[1..n]中的第几个
count array
i C[3,0,1,0] N[1,2,3,4]
0 C[0] = 3 N中第3个,N[3] = 4,在N里面删除4, N=[1,2,3]
1 C[1] = 0 N中第0个,N[0] = 1,在N里面删除1, N=[2,3]
2 C[2] = 1 N中第1个,N[1] = 3,在N里面删除3, N=[2]
3 C[3] = 0 N中第0个,N[0] = 2
所以答案是4 1 3 2
我们需要一个算法快速的得到[1..n]中第k个，并且还要快速的删除掉，我只会用线段
树。

e*y2014-12-26 08:12

19 楼

不太理解怎么用线段树解决这个问题。
能写点代码看看吗？

【在 x***7 的大作中提到】

: Count array 就是一个rank
: 表示当前数字在还存在的[1..n]中的第几个
: count array
: i C[3,0,1,0] N[1,2,3,4]
: 0 C[0] = 3 N中第3个,N[3] = 4,在N里面删除4, N=[1,2,3]
: 1 C[1] = 0 N中第0个,N[0] = 1,在N里面删除1, N=[2,3]
: 2 C[2] = 1 N中第1个,N[1] = 3,在N里面删除3, N=[2]
: 3 C[3] = 0 N中第0个,N[0] = 2
: 所以答案是4 1 3 2
: 我们需要一个算法快速的得到[1..n]中第k个，并且还要快速的删除掉，我只会用线段

x*72014-12-26 08:12

20 楼

T_T打了很多字回复的时候忘记密码了。。。。然后没了。。。
线段树嘛大概这样，我们建立一个[1..n]这个区间的线段树，每个叶子节点标记为1，
其他节点的值为这个节点下面有多少个为1的叶子节点。
【查找k大】
看左子树有多少个为1的节点，如果大于等于k，那么就在左子树找。如果不到k，那么
就在右子树找k-左子树为1的叶子节点个数。
当你找到相应的叶子节点，那么他表示的区间[l,r](l == r)，l或者r就是我们要找的[
1..n]里面的第k个数啦。
【删除】
就是把那个叶子节点标记为0，其他包含这个节点的区间当然就是num--
代码上面有人也回复了的，大概差不多。
-----
我自己写了个，测了几个简单的数据，不保证是对的。
struct TreeNode {
TreeNode *left, *right;
int val;
int l, r;
TreeNode (int _l, int _r) : l(_l), r(_r), left(nullptr), right(nullptr) {
}
TreeNode (int _val, int _l, int _r) : val(_val), l(_l), r(_r), left(
nullptr), right(nullptr) {
}
};
TreeNode* buildTree(int l, int r) {
TreeNode* root = new TreeNode(l, r);
if (l == r) {
root->val = 1;
return root;
}
int mid = (l + r) / 2;
root->left = buildTree(l, mid);
root->right = buildTree(mid + 1, r);
root->val = root->left->val + root->right->val;
return root;
}
int query(TreeNode* root, int k) {
if (root->l == root->r) return root->l;
if (root->left->val >= k) return query(root->left, k);
else return query(root->right, k - root->left->val);
}
void update(TreeNode* root, int num) {
if (root->l <= num && root->r >= num) {
root->val--;
if (root->l < root->r) {
update(root->left, num);
update(root->right, num);
}
}
}
int main() {
int n;
cin >> n;
TreeNode* root = buildTree(1, n);
for (int i = 0; i < n; i++) {
int num;
cin >> num;
int x = query(root, num + 1);
cout << x << " ";
update(root, x);
}
cout << endl;
return 0;
}

【在 e**********y 的大作中提到】

: 不太理解怎么用线段树解决这个问题。
: 能写点代码看看吗？

a*22014-12-26 08:12

21 楼

求最大的s[i]:
//就用二叉树就足够了吧，树的节点里记录比本节点小的个数
public int sln(){

BSTNode root = new BSTNode(a[n-1],0)

int result = 0;
for i in n-2:0{
//O(logn)
result = max(result,insert(root ,a[i],0));
}
return result;
}
class BSTNode{
int value;
int descendants;
BSTNode left = null;
BSTNode right = null;
}
public int insert(BSTNode root, int value, int cnt){
if(root == null)
return 0;
int result = 0;
if(root.value < value){
result += root.descendants+1;
if(root.right == null)
root.right = new BSTNode(value,result);
else
result += insert(root.right,value,root.descendants+1);
}
if(root.value > value){
if(root.left == null)
root.left = new BSTNode(value,cnt);
else
result += insert(root.left,value,cnt);
root.descendants++;
}

return result;
}

m*k2014-12-26 08:12

22 楼

oecyc 不是举出反例了么？

【在 l*******0 的大作中提到】

: 赞！

m*k2014-12-26 08:12

23 楼

看了这个，豁然开朗！
多谢多谢！

【在 x***7 的大作中提到】

m*k2014-12-26 08:12

24 楼

Tree[Now].left=a;
Tree[Now].right=b;
if(b-a>=1) {
int mid=(a+b)>>1;
Tree[Now].left=a;
build(2*Now+1 , a,mid);
Tree[Now].right=b;
build(2*Now+2,mid+1, b);
Tree[Now].cover = Tree[2*Now+1].cover + Tree[2*Now+2].cover;
}
请问
Tree[Now].left=a;
Tree[Now].right=b;
为何两遍？
if(b-a>=1)
直接test b>a 吧?

【在 o***c 的大作中提到】

e*y2014-12-26 08:12

25 楼

非常感谢，很有帮助。
见过segment tree 用array来做的。没见过你这种。
有什么书介绍segment tree比较系统的吗，想好好看一下。找了introduction to
algorithms，3rd edition, 里面没有线段树。

的[

【在 x***7 的大作中提到】

:
: T_T打了很多字回复的时候忘记密码了。。。。然后没了。。。
: 线段树嘛大概这样，我们建立一个[1..n]这个区间的线段树，每个叶子节点标记为1，
: 其他节点的值为这个节点下面有多少个为1的叶子节点。
: 【查找k大】
: 看左子树有多少个为1的节点，如果大于等于k，那么就在左子树找。如果不到k，那么
: 就在右子树找k-左子树为1的叶子节点个数。
: 当你找到相应的叶子节点，那么他表示的区间[l,r](l == r)，l或者r就是我们要找的[
: 1..n]里面的第k个数啦。
: 【删除】

w*a2014-12-26 08:12

26 楼

我有个这题的非数组线段树解法，抛砖引玉
http://www.fgdsb.com/2014/12/28/recover-count-array/

x*72014-12-26 08:12

27 楼

segment Tree用array就好了，反正又不会增加和删除节点。

【在 e**********y 的大作中提到】

: 非常感谢，很有帮助。
: 见过segment tree 用array来做的。没见过你这种。
: 有什么书介绍segment tree比较系统的吗，想好好看一下。找了introduction to
: algorithms，3rd edition, 里面没有线段树。
:
: 的[

m*k2014-12-26 08:12

28 楼

result += insert(root.right,value,root.descendants+1);
why +=?

【在 a*****2 的大作中提到】

: 求最大的s[i]:
: //就用二叉树就足够了吧，树的节点里记录比本节点小的个数
: public int sln(){
:
: BSTNode root = new BSTNode(a[n-1],0)
:
: int result = 0;
: for i in n-2:0{
: //O(logn)
: result = max(result,insert(root ,a[i],0));