2089. Find Target Indices After Sorting Array

Posted on In Words count: 1.6k Reading time ≈ 1 mins.

2089. Find Target Indices After Sorting Array

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
You are given a 0-indexed integer array nums and a target element target.

A target index is an index i such that nums[i] == target.

Return a list of the target indices of nums after sorting nums in non-decreasing order. 
If there are no target indices, return an empty list. The returned list must be sorted in increasing order.

 

Example 1:

Input: nums = [1,2,5,2,3], target = 2
Output: [1,2]
Explanation: After sorting, nums is [1,2,2,3,5].
The indices where nums[i] == 2 are 1 and 2.
Example 2:

Input: nums = [1,2,5,2,3], target = 3
Output: [3]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 3 is 3.
Example 3:

Input: nums = [1,2,5,2,3], target = 5
Output: [4]
Explanation: After sorting, nums is [1,2,2,3,5].
The index where nums[i] == 5 is 4.
Example 4:

Input: nums = [1,2,5,2,3], target = 4
Output: []
Explanation: There are no elements in nums with value 4.
 

Constraints:

1 <= nums.length <= 100
1 <= nums[i], target <= 100

难度 : Easy

思路

解法1

排序然后遍历
时间复杂度 : O(NlogN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        Arrays.sort(nums);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (target == nums[i]) {
                ans.add(i);
            } else if (target < nums[i]) {
                break;
            }
        }
        return ans;
    }
}

解法2

counting
时间复杂度 : O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> targetIndices(int[] nums, int target) {
        int cnt = 0; // total # of num == target
        int rank = 0; //total # of num < target
        for (int num : nums) {
            cnt += (num == target ? 1 : 0);
            rank += (num < target ? 1 : 0);
        }
        List<Integer> ans = new ArrayList<>();
        while (cnt > 0) {
            ans.add(rank);
            rank++;
            cnt--;
        }
        return ans;
    }
}