维护x的秩

[编程题]维护x的秩

热度指数：5044 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知一个数组A及它的大小n，在读入这串数的时候算出每个数的秩，即在当前数组中小于等于它的数的个数(不包括它自身)。从而返回一个int数组，元素为每次加入的数的秩。保证数组大小小于等于5000。

测试样例：

[1,2,3,4,5,6,7],7

返回：[0,1,2,3,4,5,6]

算法知识视频讲解

Python

霸波奔

请教各位我的为什么通不过呢？

class Rank:

def getRankOfNumber(self, A, n):
# write code here
newA = sorted(A)
cp = A.copy()
result = [0] * len(A)
for i in range(len(A) - 1, -1, -1):
result[cp.index(newA[i])] = A.index(newA[i])
A.remove(newA[i])
return result

发表于 2019-07-30 21:28:42 回复(0)

Python

华科平凡

python solution

使用bisect来做，时间复杂度为nlogn

# -*- coding:utf-8 -*-
import bisect

class Rank:
    def getRankOfNumber(self, A, n):
        res=[]
        tmp=[]
        for i in A:
            pos=bisect.bisect_left(tmp,i)
            bisect.insort(tmp,i)
            res.append(pos)
        return res

发表于 2017-10-31 17:15:30 回复(1)

Python

Yannyezixin

思路一：直接简单但空间复杂度高 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)