Posted Updated LeetCode / Mediuma minute read (About 183 words)

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

首先对intervals按照后一项的大小进行排序。（直接将两数字相减作为比较值比Integer.compare方法更快。）
贪心算法，将已取得的最大值max设置为最小整数值。
遍历intervals，如果当前interval的左侧小于max，则不能选择该interval，计数加一。
反之则可以选择interval，更新max的值为interval的最大值。
返回总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
        int max = Integer.MIN_VALUE;
        int count = 0;
        for(int[] interval : intervals){
            if(interval[0] < max){
                count++;
            }
            else{
                max = interval[1];
            }
        }
        return count;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 134 words)

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

先对数组进行排序。
遍历数组，当前一个子数组与后一个子数组有重叠时，合并数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0],b[0]));

        int i = 0;
        List<int[]> ans = new ArrayList();
        while( i < intervals.length-1 ){
            if(intervals[i][1] >= intervals[i+1][0]){
                intervals[i+1][0] = intervals[i][0];
                intervals[i+1][1] = Math.max(intervals[i][1], intervals[i+1][1]);
                intervals[i] = null;
            }
            i++;
        }
        
        for(int[] interval : intervals){
            if(interval != null){
                ans.add(interval);
            }
        }
        return ans.toArray(new int[ans.size()][2]);
    }
}
Posted Updated LeetCode / Mediuma minute read (About 176 words)

347. Top K Frequent Elements

Question

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Solution

遍历，使用哈希表保存遍历次数。
再次遍历，根据元素出现的次数将其填入优先级队列实现的大根堆。
遍历取出k个最大值。

  • getOrDefault()：
    方便的遍历并生成哈希表。
  • lambda：
    （）内表示传入的数值。
    -> 后表示返回值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ans = new int[k];
        HashMap<Integer,Integer> map = new HashMap();
        for (int num : nums){
            map.put( num, map.getOrDefault(num , 0) + 1 );
        }
        PriorityQueue<Integer> pq = new PriorityQueue((a,b) -> map.get(b) - map.get(a));
        for (int key : map.keySet()){
            pq.add(key);
        }
        for (int i = 0; i < k ; i++){
            ans[i] = pq.poll();
        }
        return ans;
    }
}
Follow

Recents

Archives

Links

×