已知一个数组A及它的大小n，在读入这串数的时候算出每个数的秩，即在当前数组中小于等于它的数的个数(不包括它自身)。从而返回一个int数组，元素为每次加入的数的秩。保证数组大小小于等于5000。
测试样例：
[1,2,3,4,5,6,7],7
返回：[0,1,2,3,4,5,6]
[编程题]维护x的秩
import java.util.*;
/*
用一个二叉查找树来维护当前已经插入的数组，小于等于该节点插入左子树内，
大于插入右子树内，递归调用。
这样，每次查询小于等于某个节点的节点数，分三种情况讨论，递归调用：
1.当前节点的值等于插入的节点的值，那么返回该节点的左子树数目就等于秩
2.当前节点的值大于插入的节点的值，那么递归调用左子树（因为该节点的本身
及其右子树都对秩没影响)
3.当前节点的值小于插入的节点的值，那么当前节点的所有左子树加上本身都是
该插入节点的秩，
然后加上插入的节点在右子树中的秩之和为改插入节点的秩
注意：1.只用记录当前节点的左子树的个数，2.每次都是先插再找出秩，所以每
次查找不会出现不在树中的情况。
*/
public class Rank {
Node root = null;
public int[] getRankOfNumber(int[] A, int n) {
int res[] = new int[n];
for (int i = 0; i < n; i++) {
res[i] = helper(A[i]);
}
return res;
}
public int helper(int a) {
if (root == null) {
root = new Node(a);
} else {
root.insert(a);
}
return root.getRank(a);
}
}
class Node {
int leftSize = 0;
Node left, right;
int val;
public Node(int v) {
val = v;
}
public void insert(int v) {
if (v <= val) {
if (left != null)
left.insert(v);
else
left = new Node(v);
leftSize++;
} else {
if (right != null)
right.insert(v);
else
right = new Node(v);
}
}
public int getRank(int v) {
if (v == val)
return leftSize;
if (v < val)
return left.getRank(v);
if (v > val)
return leftSize + 1 + right.getRank(v);
return 0;
}
}
编辑于 2015-09-10 15:16:38
回复(3)
class Rank {
public:
vector<int> getRankOfNumber(vector<int> A, int n) {
// write code here
multiset<int>::iterator iter;
vector<int> result;
multiset<int> set;
for(int i = 0 ; i <n; ++i){
set.insert(A[i]);
iter = set.upper_bound(A[i]);
int len = 0;
multiset<int>::iterator cur = set.begin();
while(cur != iter){
len++;
cur++;
}
result.push_back(len-1);
}
return result;
}
};
就是高票答案的思路，不过用了现成的库，multiset 底层实现就是一颗红黑树，通过封装好的迭代器，可以轻松算出左边有多少节点
发表于 2016-08-30 02:28:33
回复(2)
我承认 我的方法比较low。。
public static int[] getRankOfNumber(int[] A, int n) {
// write code here
int[] result = new int[n];
for(int i=1;i<n;i++){
int count =0;
for(int j=0;j<i;j++){
if(A[j]<A[i]){
count++;
}
}
result[i] = count;
}
return result;
}
编辑于 2017-07-30 21:49:00
回复(3)
class Rank:
def getRankOfNumber(self, A, n):
return [self.add(x) for x in A]
def add(self, x):
if self.head is None:
self.head = Node(x)
return 0
else:
return self.head.insert(x, 0)
def __init__(self):
self.head = None
class Node:
def __init__(self, num):
self.num = num
self.v = 0
self.r, self.l = None, None
def insert(self, x, t):
if self.num < x:
t += 1 + self.v
l = self.l
if l is None:
self.l = Node(x)
else:
return l.insert(x, t)
else:
self.v += 1
r = self.r
if r is None:
self.r = Node(x)
else:
return r.insert(x, t)
return t
发表于 2017-03-04 14:17:54
回复(0)
// 当前节点存放小于等于它的数量，在插入的时候，更新及统计
struct Node {
int val;
int count; // no. of <= val
Node* left, *right;
Node(int v) : val(v), count(1), left(NULL), right(NULL) {}
};
class Rank {
public:
vector<int> getRankOfNumber(vector<int> A, int n) {
vector<int> ret;
if (n == 0) return ret;
Node *root = new Node(A[0]);
ret.push_back(0);
// Build tree
for (int i = 1; i < A.size(); i++) {
int num = A[i];
Node* cur = root;
int cnt = 0;
while (cur) {
if (cur->val < num) {
cnt += cur->count;
if (cur->right) cur = cur->right;
else {
cur->right = new Node(num);
break;
}
} else if (cur->val == num) {
cnt += cur->count;
cur->count++;
break;
} else {
cur->count++;
if (cur->left) cur = cur->left;
else {
cur->left = new Node(num);
break;
}
}
}
ret.push_back(cnt);
}
return ret;
}
};
发表于 2016-06-13 14:38:47
回复(0)
/*
* 使用二叉查找树完成添加与秩的查询，树的添加复杂度低O(logN)
* 且对叶子节点添加左子树节点数的域：
* if d == data
* return left_size
* if d < data
* return left.getRank(d)
* if
* return left_size + 1 + right.getRank(d)
*/
public class RankNode{
public int left_size = 0;
public RankNode left, right;
public int data = 0;
public RankNode(int d) {
// TODO Auto-generated constructor stub
data = d;
}
public void insert(int d) {
// TODO Auto-generated method stub
if(d <= data){
if(left != null){
left.insert(d);
}else{
left = new RankNode(d);
}
left_size++;
}else{
if(right != null){
right.insert(d);
}else{
right = new RankNode(d);
}
}
}
public int getRank(int d) {
// TODO Auto-generated method stub
if(d == data){
return left_size;
}else if(d < data){
if(left == null){
return -1;
}else{
return left.getRank(d);
}
}else{//???
int right_rank = right == null ? -1 : right.getRank(d);
if(right_rank == -1) return -1;
return left_size + 1 + right.getRank(d);
}
}
}
public int[] getRankOfNumber(int[] A, int n) {
// write code here
if(A == null || A.length != n || n <= 0){
return null;
}
int[] ranks = new int[n];
ranks[0] = 0;
RankNode root = new RankNode(A[0]);
for(int i = 1; i < n; i++){
root.insert(A[i]);
ranks[i] = root.getRank(A[i]);
}
return ranks;
}
发表于 2016-06-11 20:16:09
回复(0)
class Rank {
public:
vector<int> getRankOfNumber(vector<int> A, int n) {
vector<int> v; set<int> s; for(int i=0;i<n;i++){ s.insert(A[i]); set<int>::iterator x = s.upper_bound(A[i]); int cnt=0; for(set<int>::iterator it=s.begin();it!=x;it++) cnt++; v.push_back(cnt-1); } return v;
}
};
发表于 2019-03-06 01:51:24
回复(0)
使用一个数组，使用二分查找的方法返回查找到插入到数组中的索引值和插入该值到数组中，每次插入都是使用二分查找，算法的复杂度为O（NlogN）
# -*- coding:utf-8 -*-
def bisect_insert(arr, n):
low, high = 0, len(arr) - 1
while low <= high:
m = (low + high) // 2
if arr[m] == n:
_r = m
while _r <= high and arr[_r] == n:
_r += 1
high = _r
arr.insert(high, n)
return high
elif arr[m] > n:
high = m - 1
else:
low = m + 1
arr.insert(low, n)
return low
class Rank:
def getRankOfNumber(self, A, n):
# write code here
arr = []
res = []
for x in A:
res.append(bisect_insert(arr, x))
return res
发表于 2018-04-07 12:41:35
回复(0)
class Rank {
public:
vector<int> getRankOfNumber(vector<int> A, int n) {
// write code here
vector<int> res(n,0);
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(A[j]<=A[i])
res[i]++;
}
}
return res;
}
};
发表于 2017-09-26 19:12:17
回复(0)
利用map的有序性质，进行计数统计。
class Rank {
public:
vector<int> getRankOfNumber(vector<int> A, int n)
{
map<int, int,greater<int>> count;
vector<int> res(n, 0);
for (int i = 0; i < n; ++i)
{
int num = -1;
++count[A[i]];
auto pos = count.find(A[i]);
while (pos != count.end())
{
num += pos->second;
++pos;
}
res[i] = num;
}
return res;
}
};
发表于 2017-06-29 20:40:18
回复(1)
最直观的插入排序变形
class Rank {
vector<int> result = {0};
//vector<int> A = {};
public:
vector<int> getRankOfNumber(vector<int> A,
int n)
{
// write code here
for (int i = 1; i < n; ++i)
{
int j;
for (j = i ; j > 0; --j)
{
if (A[j] < A[j - 1]) //i=3 j=1
{
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
}
else
break;
}
result.push_back(j);
}
return result;
}
};
发表于 2017-04-27 11:31:59
回复(0)
思路一：直接简单但空间复杂度高 O(n^2)
根据题目的描述得出
def getRankOfNumber(self, A, n):
newList = [0]
for i in range(1, n):
num = 0
for j in range(0, i):
if A[j] <= A[i]:
num += 1
newList.append(num)
return newList
思路二： 参考第一赞的思路
# -*- coding:utf-8 -*-
class Node:
def __init__(self, val):
self.leftSize = 0
self.val = val
self.left = None
self.right = None
def insert(self, val):
if self.val >= val:
if self.left is not None:
self.left.insert(val)
else:
self.left = Node(val)
self.leftSize += 1
else:
if self.right is not None:
self.right.insert(val)
else:
self.right = Node(val)
def getRank(self, val):
if self.val == val:
return self.leftSize
if self.val > val:
return self.left.getRank(val)
if self.val < val:
return self.leftSize + 1 + self.right.getRank(val)
class Rank:
def __init__(self):
self.root = None
def getRankOfNumber(self, A, n):
res = []
for i in range(n):
res.append(self.helper(A[i]))
return res
def helper(self, val):
if self.root == None:
self.root = Node(val)
else:
self.root.insert(val)
return self.root.getRank(val)
编辑于 2016-08-09 08:13:51
回复(0)
public int[] getRankOfNumber(int[] A, int n) {
LinkedList<Integer> list = new LinkedList<>();
int[] res = new int[n];
for(int i=0;i<n;i++){
Iterator<Integer> it = list.iterator();
int j = 0;
while(it.hasNext()){
if(it.next()>A[i]){
break;
}
j++;
}
res[i] = j;
list.add(j,A[i]);
}
return res;
}
发表于 2015-09-21 14:48:49
回复(0)
class Rank {
public:
vector<int> result;
struct AvlNode{
AvlNode *left;
AvlNode *right;
int height;
int data;
int leftC; //左子树结点个数
AvlNode(const int &x,AvlNode *lt,AvlNode* rt,int h = 0)
:data(x),left(lt),right(rt),height(h),leftC(0){}
};
void insert(const int &x,AvlNode *&t,int cnt){
if(t == NULL){
t = new AvlNode(x,NULL,NULL);
result.push_back(cnt);
}
else if(x < t->data)
{
t->leftC += 1;
insert(x,t->left,cnt);
if(height(t->left) - height(t->right) == 2){
if(x < t->left->data){
rotateWithLeft(t);
}else{
doubleWithLeft(t);
}
}
}else if(t->data < x){
insert(x,t->right,cnt + t->leftC + 1);
if(height(t->right) - height(t->left) == 2)
{
if(t->right->data < x)
rotateWithRight(t);
else
doubleWithRight(t);
}
}else{ //值相等
t->leftC += 1;
result.push_back(t->leftC);
}
t->height = max(height(t->left),height(t->right)) + 1;
}
void rotateWithRight(AvlNode *&k1){
AvlNode* k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->right),height(k1->left)) + 1;
k2->height = max(height(k2->right),k1->height) + 1;
if(k2->left){
k2->leftC = k2->leftC + k2->left->leftC + 1; // 更新左子结点数目
}else{
k2->leftC = 0;
} // 更新左子结点数目
k1 = k2;
}
void rotateWithLeft(AvlNode *&k2){
AvlNode* k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left),height(k2->right)) + 1;
k1->height = max(height(k1->left),k2->height) + 1;
k2->leftC = k2->leftC - k1->leftC - 1; // 更新左子树结点数
k2 = k1;
}
void doubleWithLeft(AvlNode *&k3)
{
rotateWithRight(k3->left);
rotateWithLeft(k3);
}
void doubleWithRight(AvlNode *&k3)
{
rotateWithLeft(k3->right);
rotateWithRight(k3);
}
int height(AvlNode* t) const{
return t == NULL ? - 1 : t->height;
}
vector<int> getRankOfNumber(vector<int> A, int n) {
if(n < 1) return result;
AvlNode *root = NULL;
insert(A[0],root,0);
for(int i = 1; i < A.size(); i++) insert(A[i],root,0);
return result;
}
};
复习下AVL，在结点插入的过程中直接进行判断。nlogn
编辑于 2015-08-22 20:14:51
回复(0)
class Rank {
int tree[5005];
int lowbit(int x) { return x&(-x); }
void update(int pos, int val) {
for(int i = pos; i <= 5000; i += lowbit(i))
tree[i] += val;
}
int query(int x) {
int ans = 0;
for(int i = x; i; i -= lowbit(i))
ans += tree[i];
return ans;
}
public:
vector<int> getRankOfNumber(vector<int> A, int n) {
// write code here
vector<int> B(A);
sort(B.begin(), B.end());
map<int, int> mp;
int cnt = 1;
for(int& i : B) {
if(mp.find(i) == mp.end()) mp[i] = cnt++;
}
vector<int> ans(n);
memset(tree, 0, sizeof(tree));
for(int i = 0; i < n; i++) {
ans[i] = query(mp[A[i]]);
update(mp[A[i]], 1);
}
return ans;
}
};
离散化+树状数组
发表于 2021-02-06 15:40:16
回复(0)
class Rank {
public:
vector<int> getRankOfNumber(vector<int> A, int n) {
// write code here
vector<int> result;// 存放元素的秩的
if(A.size()<=1)
{
return result;
}
result.push_back(0);
for(int i=1; i<A.size(); i++)
{
int zhi = 0;
for(int j=i-1; j>=0; j--)
{
if(A[i] >= A[j])
{
zhi++;
}
}
result.push_back(zhi);
}
return result;
}
};
发表于 2020-08-02 21:04:16
回复(0)
package com.jiading.niuke;
/**
* @program: Algorithm
* @description: 维护x的秩
* 现在我们要读入一串数，同时要求在读入每个数的时候算出它的秩，即在当前数组中小于等于它的数的个数(不包括它自身)，请设计一个高效的数据结构和算法来实现这个功能。
* 给定一个int数组A，同时给定它的大小n，请返回一个int数组，元素为每次加入的数的秩。保证数组大小小于等于5000。
* @author: JiaDing
* @create: 2020-07-31 23:08
**/
public class Rank {
public static int[] getRankOfNumber(int[] A, int n) {
int[] ans = new int[n];
Node node = null;
for (int i = 0; i < n; i++) {
if (node == null) {
node = new Node(A[i]);
ans[i] = 0;
} else {
ans[i] = node.insert(A[i]);
}
}
return ans;
}
static class Node {
int leftSize = 0;
int val = 0;
Node left = null, right = null;
public Node(int val) {
this.val = val;
}
public int insert(int val) {
if (this.val <= val) {
if (this.right != null) {
return leftSize + 1 + this.right.insert(val);
} else {
this.right = new Node(val);
return this.leftSize + 1;
}
} else {
this.leftSize++;
if (this.left != null) {
return this.left.insert(val);
} else {
this.left = new Node(val);
return 0;
}
}
}
}
public static void main(String[] args) {
int[] rankOfNumber = getRankOfNumber(new int[]{5, 1, 7, 9, 3, 4, 2}, 7);
for (int i : rankOfNumber
) {
System.out.println(i);
}
}
}
发表于 2020-07-31 23:37:47
回复(0)
问题信息
难度：
46条回答
56收藏
16097浏览
通过挑战的用户
查看代码-
2022-09-01 23:16:14
-
2022-08-17 20:36:57
-
2022-08-06 11:03:16 -
2022-07-11 22:17:31 -
2022-06-23 18:26:03
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
