b******i
发帖数: 914 | 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******4
发帖数: 94 | 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******i
发帖数: 914 | 3 具体说说，怎么mergesort法？
【在 k******4 的大作中提到】
: merge sort变种
| s*********3
发帖数: 25 | 4 merge sort 只是用于计算总的逆序数，对于单个的逆序数的话，时间复杂度应该还是n
^2 | k******4
发帖数: 94 | 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; i
retv[C[i].idx] = C[i].count;
return retv;
} | k******4
发帖数: 94 | 6 看成要返回每个s[i], 上面的程序修改下，countBigger中返回retv中的最大值就可以
了。 | h*********r
发帖数: 76 | 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)
| o***c
发帖数: 32 | 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*********r
发帖数: 76 | 9 多谢指正
不过现在new grad都要考线段树了？
【在 o***c 的大作中提到】
: 明显不对，ex: 3 5 1 4 2
: 应该是使用点树，线段树或树状数组做才能保证O(nlogn)的复杂度。
| o***c
发帖数: 32 | 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].left
del(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;i
cin >> val[i];
}
s.build(0, 0, n-1);
for(int i=0;i
int x = s.Count(0,val[i]+1);
cout << x + 1 << endl;
s.del(0, x);
}
return 0;
}
【在 h*********r 的大作中提到】
: 多谢指正
: 不过现在new grad都要考线段树了？
| | | b******i
发帖数: 914 | 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*******9
发帖数: 138 | 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********n
发帖数: 165 | 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)
| b******i
发帖数: 914 | 14 请问变种你说的mergesort具体是怎么做来着？不用线段树吗
【在 p********n 的大作中提到】
:
: 这个变种是用原数组求 count array 用merge sort做可以。
: 但反方向，用count array 求原来数组 O(nlogn)比较麻烦，应该分好几步，有一步是
: 建立一个balanced BST,每个node存储它left subtree的node的个数。
| m*****k
发帖数: 731 | 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*******0
发帖数: 95 | 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*******0
发帖数: 95 | 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
| x***7
发帖数: 11 | 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**********y
发帖数: 128 | 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***7
发帖数: 11 | 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*****2
发帖数: 96 | 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*****k
发帖数: 731 | 22 oecyc 不是举出反例了么？
【在 l*******0 的大作中提到】
: 赞！
| m*****k
发帖数: 731 | 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个，并且还要快速的删除掉，我只会用线段
| m*****k
发帖数: 731 | 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;
| e**********y
发帖数: 128 | 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****a
发帖数: 710 | | x***7
发帖数: 11 | 27 segment Tree用array就好了，反正又不会增加和删除节点。
【在 e**********y 的大作中提到】
: 非常感谢，很有帮助。
: 见过segment tree 用array来做的。没见过你这种。
: 有什么书介绍segment tree比较系统的吗，想好好看一下。找了introduction to
: algorithms，3rd edition, 里面没有线段树。
:
: 的[
| m*****k
发帖数: 731 | 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));
| t*****a
发帖数: 106 | 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));
| a*****a
发帖数: 46 | 30 http://bit.ly/1w6BFpN 一个可以运行的比较诡异的实现，binary index tree来恢复原来的数组 | | | z***m
发帖数: 1602 | 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个，并且还要快速的删除掉，我只会用线段
|
|
