Binary Indexed Tree
Segment Tree
Array
Binary Search
Divide and Conquer
Ordered Set
Merge Sort
Description
Given an integer array nums
, return an integer array counts
where counts[i]
is the number of smaller elements to the right of nums[i]
.
Example 1:
Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Example 2:
Input: nums = [-1]
Output: [0]
Example 3:
Input: nums = [-1,-1]
Output: [0,0]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 class BinaryIndexedTree :
def __init__ ( self , n ):
self . n = n
self . c = [ 0 ] * ( n + 1 )
@staticmethod
def lowbit ( x ):
return x & - x
def update ( self , x , delta ):
while x <= self . n :
self . c [ x ] += delta
x += BinaryIndexedTree . lowbit ( x )
def query ( self , x ):
s = 0
while x > 0 :
s += self . c [ x ]
x -= BinaryIndexedTree . lowbit ( x )
return s
class Solution :
def countSmaller ( self , nums : List [ int ]) -> List [ int ]:
alls = sorted ( set ( nums ))
m = { v : i for i , v in enumerate ( alls , 1 )}
tree = BinaryIndexedTree ( len ( m ))
ans = []
for v in nums [:: - 1 ]:
x = m [ v ]
tree . update ( x , 1 )
ans . append ( tree . query ( x - 1 ))
return ans [:: - 1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 class Solution {
public List < Integer > countSmaller ( int [] nums ) {
Set < Integer > s = new HashSet <> ();
for ( int v : nums ) {
s . add ( v );
}
List < Integer > alls = new ArrayList <> ( s );
alls . sort ( Comparator . comparingInt ( a -> a ));
int n = alls . size ();
Map < Integer , Integer > m = new HashMap <> ( n );
for ( int i = 0 ; i < n ; ++ i ) {
m . put ( alls . get ( i ), i + 1 );
}
BinaryIndexedTree tree = new BinaryIndexedTree ( n );
LinkedList < Integer > ans = new LinkedList <> ();
for ( int i = nums . length - 1 ; i >= 0 ; -- i ) {
int x = m . get ( nums [ i ] );
tree . update ( x , 1 );
ans . addFirst ( tree . query ( x - 1 ));
}
return ans ;
}
}
class BinaryIndexedTree {
private int n ;
private int [] c ;
public BinaryIndexedTree ( int n ) {
this . n = n ;
c = new int [ n + 1 ] ;
}
public void update ( int x , int delta ) {
while ( x <= n ) {
c [ x ] += delta ;
x += lowbit ( x );
}
}
public int query ( int x ) {
int s = 0 ;
while ( x > 0 ) {
s += c [ x ] ;
x -= lowbit ( x );
}
return s ;
}
public static int lowbit ( int x ) {
return x & - x ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 class BinaryIndexedTree {
public :
int n ;
vector < int > c ;
BinaryIndexedTree ( int _n )
: n ( _n )
, c ( _n + 1 ) {}
void update ( int x , int delta ) {
while ( x <= n ) {
c [ x ] += delta ;
x += lowbit ( x );
}
}
int query ( int x ) {
int s = 0 ;
while ( x > 0 ) {
s += c [ x ];
x -= lowbit ( x );
}
return s ;
}
int lowbit ( int x ) {
return x & - x ;
}
};
class Solution {
public :
vector < int > countSmaller ( vector < int >& nums ) {
unordered_set < int > s ( nums . begin (), nums . end ());
vector < int > alls ( s . begin (), s . end ());
sort ( alls . begin (), alls . end ());
unordered_map < int , int > m ;
int n = alls . size ();
for ( int i = 0 ; i < n ; ++ i ) m [ alls [ i ]] = i + 1 ;
BinaryIndexedTree * tree = new BinaryIndexedTree ( n );
vector < int > ans ( nums . size ());
for ( int i = nums . size () - 1 ; i >= 0 ; -- i ) {
int x = m [ nums [ i ]];
tree -> update ( x , 1 );
ans [ i ] = tree -> query ( x - 1 );
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 type BinaryIndexedTree struct {
n int
c [] int
}
func newBinaryIndexedTree ( n int ) * BinaryIndexedTree {
c := make ([] int , n + 1 )
return & BinaryIndexedTree { n , c }
}
func ( this * BinaryIndexedTree ) lowbit ( x int ) int {
return x & - x
}
func ( this * BinaryIndexedTree ) update ( x , delta int ) {
for x <= this . n {
this . c [ x ] += delta
x += this . lowbit ( x )
}
}
func ( this * BinaryIndexedTree ) query ( x int ) int {
s := 0
for x > 0 {
s += this . c [ x ]
x -= this . lowbit ( x )
}
return s
}
func countSmaller ( nums [] int ) [] int {
s := make ( map [ int ] bool )
for _ , v := range nums {
s [ v ] = true
}
var alls [] int
for v := range s {
alls = append ( alls , v )
}
sort . Ints ( alls )
m := make ( map [ int ] int )
for i , v := range alls {
m [ v ] = i + 1
}
ans := make ([] int , len ( nums ))
tree := newBinaryIndexedTree ( len ( alls ))
for i := len ( nums ) - 1 ; i >= 0 ; i -- {
x := m [ nums [ i ]]
tree . update ( x , 1 )
ans [ i ] = tree . query ( x - 1 )
}
return ans
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 class Node :
def __init__ ( self ):
self . l = 0
self . r = 0
self . v = 0
class SegmentTree :
def __init__ ( self , n ):
self . tr = [ Node () for _ in range ( n << 2 )]
self . build ( 1 , 1 , n )
def build ( self , u , l , r ):
self . tr [ u ] . l = l
self . tr [ u ] . r = r
if l == r :
return
mid = ( l + r ) >> 1
self . build ( u << 1 , l , mid )
self . build ( u << 1 | 1 , mid + 1 , r )
def modify ( self , u , x , v ):
if self . tr [ u ] . l == x and self . tr [ u ] . r == x :
self . tr [ u ] . v += v
return
mid = ( self . tr [ u ] . l + self . tr [ u ] . r ) >> 1
if x <= mid :
self . modify ( u << 1 , x , v )
else :
self . modify ( u << 1 | 1 , x , v )
self . pushup ( u )
def query ( self , u , l , r ):
if self . tr [ u ] . l >= l and self . tr [ u ] . r <= r :
return self . tr [ u ] . v
mid = ( self . tr [ u ] . l + self . tr [ u ] . r ) >> 1
v = 0
if l <= mid :
v += self . query ( u << 1 , l , r )
if r > mid :
v += self . query ( u << 1 | 1 , l , r )
return v
def pushup ( self , u ):
self . tr [ u ] . v = self . tr [ u << 1 ] . v + self . tr [ u << 1 | 1 ] . v
class Solution :
def countSmaller ( self , nums : List [ int ]) -> List [ int ]:
s = sorted ( set ( nums ))
m = { v : i for i , v in enumerate ( s , 1 )}
tree = SegmentTree ( len ( s ))
ans = []
for v in nums [:: - 1 ]:
x = m [ v ]
ans . append ( tree . query ( 1 , 1 , x - 1 ))
tree . modify ( 1 , x , 1 )
return ans [:: - 1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85 class Solution {
public List < Integer > countSmaller ( int [] nums ) {
Set < Integer > s = new HashSet <> ();
for ( int v : nums ) {
s . add ( v );
}
List < Integer > alls = new ArrayList <> ( s );
alls . sort ( Comparator . comparingInt ( a -> a ));
int n = alls . size ();
Map < Integer , Integer > m = new HashMap <> ( n );
for ( int i = 0 ; i < n ; ++ i ) {
m . put ( alls . get ( i ), i + 1 );
}
SegmentTree tree = new SegmentTree ( n );
LinkedList < Integer > ans = new LinkedList <> ();
for ( int i = nums . length - 1 ; i >= 0 ; -- i ) {
int x = m . get ( nums [ i ] );
tree . modify ( 1 , x , 1 );
ans . addFirst ( tree . query ( 1 , 1 , x - 1 ));
}
return ans ;
}
}
class Node {
int l ;
int r ;
int v ;
}
class SegmentTree {
private Node [] tr ;
public SegmentTree ( int n ) {
tr = new Node [ 4 * n ] ;
for ( int i = 0 ; i < tr . length ; ++ i ) {
tr [ i ] = new Node ();
}
build ( 1 , 1 , n );
}
public void build ( int u , int l , int r ) {
tr [ u ] . l = l ;
tr [ u ] . r = r ;
if ( l == r ) {
return ;
}
int mid = ( l + r ) >> 1 ;
build ( u << 1 , l , mid );
build ( u << 1 | 1 , mid + 1 , r );
}
public void modify ( int u , int x , int v ) {
if ( tr [ u ] . l == x && tr [ u ] . r == x ) {
tr [ u ] . v += v ;
return ;
}
int mid = ( tr [ u ] . l + tr [ u ] . r ) >> 1 ;
if ( x <= mid ) {
modify ( u << 1 , x , v );
} else {
modify ( u << 1 | 1 , x , v );
}
pushup ( u );
}
public void pushup ( int u ) {
tr [ u ] . v = tr [ u << 1 ] . v + tr [ u << 1 | 1 ] . v ;
}
public int query ( int u , int l , int r ) {
if ( tr [ u ] . l >= l && tr [ u ] . r <= r ) {
return tr [ u ] . v ;
}
int mid = ( tr [ u ] . l + tr [ u ] . r ) >> 1 ;
int v = 0 ;
if ( l <= mid ) {
v += query ( u << 1 , l , r );
}
if ( r > mid ) {
v += query ( u << 1 | 1 , l , r );
}
return v ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72 class Node {
public :
int l ;
int r ;
int v ;
};
class SegmentTree {
public :
vector < Node *> tr ;
SegmentTree ( int n ) {
tr . resize ( 4 * n );
for ( int i = 0 ; i < tr . size (); ++ i ) tr [ i ] = new Node ();
build ( 1 , 1 , n );
}
void build ( int u , int l , int r ) {
tr [ u ] -> l = l ;
tr [ u ] -> r = r ;
if ( l == r ) return ;
int mid = ( l + r ) >> 1 ;
build ( u << 1 , l , mid );
build ( u << 1 | 1 , mid + 1 , r );
}
void modify ( int u , int x , int v ) {
if ( tr [ u ] -> l == x && tr [ u ] -> r == x ) {
tr [ u ] -> v += v ;
return ;
}
int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ;
if ( x <= mid )
modify ( u << 1 , x , v );
else
modify ( u << 1 | 1 , x , v );
pushup ( u );
}
void pushup ( int u ) {
tr [ u ] -> v = tr [ u << 1 ] -> v + tr [ u << 1 | 1 ] -> v ;
}
int query ( int u , int l , int r ) {
if ( tr [ u ] -> l >= l && tr [ u ] -> r <= r ) return tr [ u ] -> v ;
int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ;
int v = 0 ;
if ( l <= mid ) v += query ( u << 1 , l , r );
if ( r > mid ) v += query ( u << 1 | 1 , l , r );
return v ;
}
};
class Solution {
public :
vector < int > countSmaller ( vector < int >& nums ) {
unordered_set < int > s ( nums . begin (), nums . end ());
vector < int > alls ( s . begin (), s . end ());
sort ( alls . begin (), alls . end ());
unordered_map < int , int > m ;
int n = alls . size ();
for ( int i = 0 ; i < n ; ++ i ) m [ alls [ i ]] = i + 1 ;
SegmentTree * tree = new SegmentTree ( n );
vector < int > ans ( nums . size ());
for ( int i = nums . size () - 1 ; i >= 0 ; -- i ) {
int x = m [ nums [ i ]];
tree -> modify ( 1 , x , 1 );
ans [ i ] = tree -> query ( 1 , 1 , x - 1 );
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 type Pair struct {
val int
index int
}
var (
tmp [] Pair
count [] int
)
func countSmaller ( nums [] int ) [] int {
tmp , count = make ([] Pair , len ( nums )), make ([] int , len ( nums ))
array := make ([] Pair , len ( nums ))
for i , v := range nums {
array [ i ] = Pair { val : v , index : i }
}
sorted ( array , 0 , len ( array ) - 1 )
return count
}
func sorted ( arr [] Pair , low , high int ) {
if low >= high {
return
}
mid := low + ( high - low ) / 2
sorted ( arr , low , mid )
sorted ( arr , mid + 1 , high )
merge ( arr , low , mid , high )
}
func merge ( arr [] Pair , low , mid , high int ) {
left , right := low , mid + 1
idx := low
for left <= mid && right <= high {
if arr [ left ]. val <= arr [ right ]. val {
count [ arr [ left ]. index ] += right - mid - 1
tmp [ idx ], left = arr [ left ], left + 1
} else {
tmp [ idx ], right = arr [ right ], right + 1
}
idx ++
}
for left <= mid {
count [ arr [ left ]. index ] += right - mid - 1
tmp [ idx ] = arr [ left ]
idx , left = idx + 1 , left + 1
}
for right <= high {
tmp [ idx ] = arr [ right ]
idx , right = idx + 1 , right + 1
}
// ζεΊ
for i := low ; i <= high ; i ++ {
arr [ i ] = tmp [ i ]
}
}
GitHub