8月算法训练------第三天（排序）解题报告

题目类型：排序
题目难度：简单

第一题、1464. 数组中两元素的最大乘积

1. 题目链接：1464. 数组中两元素的最大乘积
2. 思路分析：
   这一题还是比较简单的，只需将数组进行排序，然后将最大的数乘第二大的数返回就行。
3. 代码：

class Solution {
    public int maxProduct(int[] nums) {
        Arrays.sort(nums);
        return (nums[nums.length-2] - 1) * (nums[nums.length-1] - 1);
    }
}
1
2
3
4
5
6

第二题、1636. 按照频率将数组升序排序

1. 题目链接：1636. 按照频率将数组升序排序
2. 思路分析：
   题中所给的条件位1 <= nums.length <= 100和-100 <= nums[i] <= 100，我们先统计数组中nums[i]出现的次数，因为nums[i]可能为负数，所以要将它加100变成0 <= nums[i] <= 200，这样就需要一个长度为201的数组来存储nums中的数出现的频率，然后再将数组按照其频率赋予其新值，这个规则就是：nums[i] = 201 * cnts[nums[i] + 100] - nums[i] + 100;，根据赋予的新值排序，然后再将其值变回来就能得到答案了。
3. 代码：

class Solution {
    public int[] frequencySort(int[] nums) {
        int[] cnts = new int[201];
        for (int n : nums){
            cnts[n + 100] ++;
        }
        for (int i = 0; i < nums.length; i++){
            nums[i] = 201 * cnts[nums[i] + 100] - nums[i] + 100;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            nums[i] = 100 - nums[i] % 201;
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第三题、1287. 有序数组中出现次数超过25%的元素

1. 题目链接：1287. 有序数组中出现次数超过25%的元素
2. 思路分析：
   用一个HashMap来存储数组中的值，key为数组中的值，value为key在数组中出现的次数，然后遍历这个HashMap当value值大于25%时，就将这个对应的key值返回。
3. 代码：

class Solution {
    public int findSpecialInteger(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap();
        int n = arr.length;
        int m = n * 25 / 100;
        for(int i : arr){
            if(map.containsKey(i)){
                int a = map.get(i);
                map.replace(i, a, a+1);
            }else{
                map.put(i, 1);
            }
        }
        Set entrySet = map.entrySet();
        Iterator it = entrySet.iterator();
        while(it.hasNext()){
            Map.Entry entry = (Map.Entry) (it.next());
            Object key = entry.getKey();
            Object value = entry.getValue();
            if((int)value > m){
                return (int) key; 
            }
        }
        return 0;
    }
}
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

第四题、436. 寻找右区间

1. 题目链接：436. 寻找右区间

2. 思路分析：
   首先我们可以对区间 intervals 的起始位置进行排序，并将每个起始位置 intervals[i][0] 对应的索引 i 存储在数组 startIntervals中，然后枚举每个区间 ii 的右端点intervals[i][1]，利用二分查找来找到大于等于intervals[i][1]的最小值val即可，此时区间i对应的右侧区间即为右端点val对应的索引。

3. 代码：

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] startIntervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            startIntervals[i][0] = intervals[i][0];
            startIntervals[i][1] = i;
        }
        Arrays.sort(startIntervals, (o1, o2) -> o1[0] - o2[0]);

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            int target = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (startIntervals[mid][0] >= intervals[i][1]) {
                    target = startIntervals[mid][1];
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            ans[i] = target;
        }
        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