480-滑动窗口中位数
数据结构和算法
5 分钟 读完 (大约 814 个字) 0次访问

480-滑动窗口中位数

力扣480

https://leetcode-cn.com/problems/sliding-window-median/

题目

首先考虑暴力法，每次截取其中的窗口并进行排序，然后取中位数，O(n^2 * logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public double[] medianSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length == 0){
        return new double[]{0.0};
    }
    double[] res = new double[nums.length - k + 1];
    for (int i = 0; i < nums.length - k + 1; i++) {
        int[] arr = new int[k];
        System.arraycopy(nums, i, arr, 0, k);

        //排序
        Arrays.sort(arr);
        int mid = k / 2;
        if (k % 2 == 0){
            res[i] = arr[mid - 1] / 2.0 + arr[mid] / 2.0;
        }else{
            res[i] = arr[mid];
        }
    }

    return res;
}

滑动窗口方法，第一次窗口填值并排好序，后面的只需要删除旧的窗口元素和加入新的窗口元素，且加入新窗口元素时可以通过二分查找应该插入的位置，O(n^2)

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
public double[] medianSlidingWindow2(int[] nums, int k) {
    if (nums == null || nums.length == 0){
        return new double[0];
    }

    double[] res = new double[nums.length - k + 1];
    int mid = k / 2;
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        list.add(nums[i]);
    }
    Collections.sort(list);

    for (int i = 0; i < nums.length - k + 1; i++) {
        //加入结果集
        if (k % 2 == 0){
            res[i] = list.get(mid - 1) / 2.0 + list.get(mid) / 2.0;
        }else{
            res[i] = list.get(mid);
        }

        if (i + k == nums.length) break;

        //去掉一个
        list.remove(Integer.valueOf(nums[i]));

        //插入新的
        int idx = findIndex(list, nums[i + k]);
        list.add(idx, nums[i + k]);
    }

    return res;
}

/**
 * 二分查找
 */
public int findIndex(List<Integer> nums, int target){
    int l = 0, r = nums.size() - 1, mid;

    while(l <= r){
        mid = l + (r - l) / 2;
        if(target < nums.get(mid)) r = mid - 1;
        else if(target == nums.get(mid)) return mid;
        else if(target > nums.get(mid)) l = mid + 1;
    }
    return l;
}

最终优化：和2思想一样，只是该题其实窗口从头到尾都是有序的，细节优化为全局都使用二分，O(n * logn)

  • 优化1：第一次窗口填值就可以通过二分查找插入对应位置，无需排序
  • 优化2：不止是加入新元素的时候用二分，删除旧元素的时候也可通过二分查找位置，这样调用remove就不用遍历查找了
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
public double[] medianSlidingWindow3(int[] nums, int k) {
    if (nums == null || nums.length == 0){
        return new double[0];
    }

    double[] res = new double[nums.length - k + 1];
    int mid = k / 2;
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < k; i++) {
        //优化：插入的时候就可以再利用二分查找顺便排好序
        int idx = findIndex(list, nums[i]);
        list.add(idx, nums[i]);
    }

    for (int i = 0; i < nums.length - k + 1; i++) {
        //加入结果集
        if (k % 2 == 0){
            res[i] = list.get(mid - 1) / 2.0 + list.get(mid) / 2.0;
        }else{
            res[i] = list.get(mid);
        }

        if (i + k == nums.length) break;

        //去掉一个
        //优化：去掉的时候也可以利用二分查找删除，就可以remove下标而不是remove元素
        int idx = findIndex(list, nums[i]);
        list.remove(idx);

        //插入新的
        idx = findIndex(list, nums[i + k]);
        list.add(idx, nums[i + k]);
    }

    return res;
}

//findIndex方法和解法2完全一致

python实现

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
def medianSlidingWindow3(self, nums: List[int], k: int) -> List[float]:
    if nums is None or len(nums) == 0:
        return []

    mid = k // 2
    res = []
    li = nums[: k]
    li.sort()

    for i, num in enumerate(nums):
        # 加入结果集
        if k % 2 == 0:
            res.append(li[mid - 1] / 2 + li[mid] / 2)
        else:
            res.append(li[mid])

        if i + k == len(nums):
            break

        # 去掉一个
        idx = self.find_index(li, nums[i])
        del(li[idx])

        # 插入新的
        idx = self.find_index(li, nums[i + k])
        li.insert(idx, nums[i + k])

    return res

def find_index(self, nums, target) -> int:
    """
    二分查找
    """
    l, r, mid = 0, len(nums) - 1, 0

    while l <= r:
        mid = l + (r - l) // 2
        if target < nums[mid]:
            r = mid - 1
        elif target == nums[mid]:
            return mid
        else:
            l = mid + 1

    return l

其他滑动窗口类型的题目可以点击这里

1208-尽可能使字符串相等
424-替换后的最长重复字符
关注我

分类

标签云

DL/ML http lintcode markdown mysql spring springcloud 二分查找 剑指offer 力扣 加密 动态规划 单调栈 回溯 字符串 学习记录 开发 排序 数据结构 栈 树 游戏和引擎 笔试 笔试面试 算法 递归

推荐阅读

推荐阅读

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×