avatar
问一道G家热题# JobHunting - 待字闺中
b*i
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)
目测可能方法差不多。
谢谢!
avatar
k*4
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)

avatar
b*i
3
具体说说,怎么mergesort法?

【在 k******4 的大作中提到】
: merge sort变种
avatar
s*3
4
merge sort 只是用于计算总的逆序数,对于单个的逆序数的话,时间复杂度应该还是n
^2
avatar
k*4
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;
}
avatar
k*4
6
看成要返回每个s[i], 上面的程序修改下,countBigger中返回retv中的最大值就可以
了。
avatar
h*r
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 的大作中提到】
: 考古了半天,没有发现什么好的解法,望大牛指教
: 给定一个数字数组 ,其中每个元素是从末端数小于原数组中该元素的个数。求原数组。
: 原数组中元素是 从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)

avatar
o*c
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

avatar
h*r
9
多谢指正
不过现在new grad都要考线段树了?

【在 o***c 的大作中提到】
: 明显不对,ex: 3 5 1 4 2
: 应该是使用点树,线段树或树状数组做才能保证O(nlogn)的复杂度。

avatar
o*c
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都要考线段树了?

avatar
b*i
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;

avatar
x*9
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;
};
avatar
p*n
13

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

【在 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)

avatar
b*i
14
请问变种你说的mergesort具体是怎么做来着?不用线段树吗

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

avatar
m*k
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

avatar
l*0
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;
}
}
avatar
l*0
17
赞!

【在 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

avatar
x*7
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个,并且还要快速的删除掉,我只会用线段
树。
avatar
e*y
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个,并且还要快速的删除掉,我只会用线段

avatar
x*7
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 的大作中提到】
: 不太理解怎么用线段树解决这个问题。
: 能写点代码看看吗?

avatar
a*2
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;
}
avatar
m*k
22
oecyc 不是举出反例了么?

【在 l*******0 的大作中提到】
: 赞!
avatar
m*k
23
看了这个,豁然开朗!
多谢多谢!

【在 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个,并且还要快速的删除掉,我只会用线段

avatar
m*k
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 的大作中提到】
: 我同学两周前onsite被考到了,不过此题线段树写起来也方便。
: #define Maxn 10000
: int val[1010];
: class Segment_Tree {
: private:
: struct Node {
: int left,right,cover;
: };
: Node Tree[Maxn];
: int Number, c, d;

avatar
e*y
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个数啦。
: 【删除】

avatar
x*7
27
segment Tree用array就好了,反正又不会增加和删除节点。

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

avatar
m*k
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));

avatar
t*a
29
得是balanced tree才能保证O(nlog(n)), 否则还是O(n^2)

【在 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));

avatar
a*a
30
http://bit.ly/1w6BFpN 一个可以运行的比较诡异的实现,binary index tree来恢复原来的数组
avatar
z*m
31
赞,这个应该是不用线段树的方法了

【在 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个,并且还要快速的删除掉,我只会用线段

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。