数组
哈希表
排序
模拟
堆(优先队列)
题目描述
给你一个长度为 n
下标从 0 开始的正整数数组 nums
。
同时给你一个长度为 m
的二维操作数组 queries
,其中 queries[i] = [indexi , ki ]
。
一开始,数组中的所有元素都 未标记 。
你需要依次对数组执行 m
次操作,第 i
次操作中,你需要执行:
如果下标 indexi
对应的元素还没标记,那么标记这个元素。
然后标记 ki
个数组中还没有标记的 最小 元素。如果有元素的值相等,那么优先标记它们中下标较小的。如果少于 ki
个未标记元素存在,那么将它们全部标记。
请你返回一个长度为 m
的数组 answer
,其中 answer[i]
是第 i
次操作后数组中还没标记元素的 和 。
示例 1:
输入: nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]
输出: [8,3,0]
解释:
我们依次对数组做以下操作:
标记下标为 1
的元素,同时标记 2
个未标记的最小元素。标记完后数组为 nums = [1 ,2 ,2,1 ,2,3,1]
。未标记元素的和为 2 + 2 + 3 + 1 = 8
。
标记下标为 3
的元素,由于它已经被标记过了,所以我们忽略这次标记,同时标记最靠前的 3
个未标记的最小元素。标记完后数组为 nums = [1 ,2 ,2 ,1 ,2 ,3,1 ]
。未标记元素的和为 3
。
标记下标为 4
的元素,由于它已经被标记过了,所以我们忽略这次标记,同时标记最靠前的 2
个未标记的最小元素。标记完后数组为 nums = [1 ,2 ,2 ,1 ,2 ,3 ,1 ]
。未标记元素的和为 0
。
示例 2:
输入: nums = [1,4,2,3], queries = [[0,1]]
输出: [7]
解释: 我们执行一次操作,将下标为 0
处的元素标记,并且标记最靠前的 1
个未标记的最小元素。标记完后数组为 nums = [1 ,4,2 ,3]
。未标记元素的和为 4 + 3 = 7
。
提示:
n == nums.length
m == queries.length
1 <= m <= n <= 105
1 <= nums[i] <= 105
queries[i].length == 2
0 <= indexi , ki <= n - 1
解法
方法一:排序 + 模拟
我们先计算出数组 n u m s nums n u m s 的总和 s s s ,定义一个数组 m a r k mark ma r k 用来标记数组中的元素是否被标记过,初始化所有元素都未被标记。
然后我们创建一个数组 a r r arr a rr ,数组中的每个元素是一个二元组 ( x , i ) (x, i) ( x , i ) ,表示数组中的第 i i i 个元素的值为 x x x 。我们对数组 a r r arr a rr 按照元素的值进行排序,如果元素的值相等,我们按照下标从小到大的顺序进行排序。
接下来我们遍历数组 q u e r i e s queries q u er i es ,对于每个查询 [ i n d e x , k ] [index, k] [ in d e x , k ] ,我们首先判断下标 i n d e x index in d e x 对应的元素是否被标记过,如果没有被标记过,我们将其标记,并且将 s s s 减去下标 i n d e x index in d e x 对应的元素的值。然后我们遍历数组 a r r arr a rr ,对于每个元素 ( x , i ) (x, i) ( x , i ) ,如果元素 i i i 没有被标记过,我们将其标记,并且将 s s s 减去元素 i i i 对应的值 x x x ,直到 k k k 为 0 0 0 或者数组 a r r arr a rr 遍历完。然后我们将 s s s 加入答案数组中。
遍历完所有的查询后,我们就得到了答案数组。
时间复杂度 O ( n × log n ) O(n \times \log n) O ( n × log n ) ,空间复杂度 O ( n ) O(n) O ( n ) 。其中 n n n 是数组 n u m s nums n u m s 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def unmarkedSumArray ( self , nums : List [ int ], queries : List [ List [ int ]]) -> List [ int ]:
n = len ( nums )
s = sum ( nums )
mark = [ False ] * n
arr = sorted (( x , i ) for i , x in enumerate ( nums ))
j = 0
ans = []
for index , k in queries :
if not mark [ index ]:
mark [ index ] = True
s -= nums [ index ]
while k and j < n :
if not mark [ arr [ j ][ 1 ]]:
mark [ arr [ j ][ 1 ]] = True
s -= arr [ j ][ 0 ]
k -= 1
j += 1
ans . append ( s )
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 class Solution {
public long [] unmarkedSumArray ( int [] nums , int [][] queries ) {
int n = nums . length ;
long s = Arrays . stream ( nums ). asLongStream (). sum ();
boolean [] mark = new boolean [ n ] ;
int [][] arr = new int [ n ][ 0 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
arr [ i ] = new int [] { nums [ i ] , i };
}
Arrays . sort ( arr , ( a , b ) -> a [ 0 ] == b [ 0 ] ? a [ 1 ] - b [ 1 ] : a [ 0 ] - b [ 0 ] );
int m = queries . length ;
long [] ans = new long [ m ] ;
for ( int i = 0 , j = 0 ; i < m ; ++ i ) {
int index = queries [ i ][ 0 ] , k = queries [ i ][ 1 ] ;
if ( ! mark [ index ] ) {
mark [ index ] = true ;
s -= nums [ index ] ;
}
for (; k > 0 && j < n ; ++ j ) {
if ( ! mark [ arr [ j ][ 1 ]] ) {
mark [ arr [ j ][ 1 ]] = true ;
s -= arr [ j ][ 0 ] ;
-- k ;
}
}
ans [ i ] = s ;
}
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 class Solution {
public :
vector < long long > unmarkedSumArray ( vector < int >& nums , vector < vector < int >>& queries ) {
int n = nums . size ();
long long s = accumulate ( nums . begin (), nums . end (), 0L L );
vector < bool > mark ( n );
vector < pair < int , int >> arr ;
for ( int i = 0 ; i < n ; ++ i ) {
arr . emplace_back ( nums [ i ], i );
}
sort ( arr . begin (), arr . end ());
vector < long long > ans ;
int m = queries . size ();
for ( int i = 0 , j = 0 ; i < m ; ++ i ) {
int index = queries [ i ][ 0 ], k = queries [ i ][ 1 ];
if ( ! mark [ index ]) {
mark [ index ] = true ;
s -= nums [ index ];
}
for (; k && j < n ; ++ j ) {
if ( ! mark [ arr [ j ]. second ]) {
mark [ arr [ j ]. second ] = true ;
s -= arr [ j ]. first ;
-- k ;
}
}
ans . push_back ( s );
}
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 func unmarkedSumArray ( nums [] int , queries [][] int ) [] int64 {
n := len ( nums )
var s int64
for _ , x := range nums {
s += int64 ( x )
}
mark := make ([] bool , n )
arr := make ([][ 2 ] int , 0 , n )
for i , x := range nums {
arr = append ( arr , [ 2 ] int { x , i })
}
sort . Slice ( arr , func ( i , j int ) bool {
if arr [ i ][ 0 ] == arr [ j ][ 0 ] {
return arr [ i ][ 1 ] < arr [ j ][ 1 ]
}
return arr [ i ][ 0 ] < arr [ j ][ 0 ]
})
ans := make ([] int64 , len ( queries ))
j := 0
for i , q := range queries {
index , k := q [ 0 ], q [ 1 ]
if ! mark [ index ] {
mark [ index ] = true
s -= int64 ( nums [ index ])
}
for ; k > 0 && j < n ; j ++ {
if ! mark [ arr [ j ][ 1 ]] {
mark [ arr [ j ][ 1 ]] = true
s -= int64 ( arr [ j ][ 0 ])
k --
}
}
ans [ i ] = s
}
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 function unmarkedSumArray ( nums : number [], queries : number [][]) : number [] {
const n = nums . length ;
let s = nums . reduce (( acc , x ) => acc + x , 0 );
const mark : boolean [] = Array ( n ). fill ( false );
const arr = nums . map (( x , i ) => [ x , i ]);
arr . sort (( a , b ) => ( a [ 0 ] === b [ 0 ] ? a [ 1 ] - b [ 1 ] : a [ 0 ] - b [ 0 ]));
let j = 0 ;
const ans : number [] = [];
for ( let [ index , k ] of queries ) {
if ( ! mark [ index ]) {
mark [ index ] = true ;
s -= nums [ index ];
}
for (; k && j < n ; ++ j ) {
if ( ! mark [ arr [ j ][ 1 ]]) {
mark [ arr [ j ][ 1 ]] = true ;
s -= arr [ j ][ 0 ];
-- k ;
}
}
ans . push ( s );
}
return ans ;
}
GitHub