LeetCode 1200. 最小绝对差

Categories:

题目描述
思路分析
1. 解法一：排序 + 一次扫描（推荐）
相似题目

题目描述

✅ 1200. 最小绝对差

思路分析

解法一：排序 + 一次扫描（推荐）

核心思路：

将数组排序后，相邻元素差值最小。

先扫描得到最小差 minDiff，再二次扫描收集所有差值等于 minDiff 的相邻对。

复杂度分析：

时间复杂度：O(n log n)，排序为主。

空间复杂度：O(1)（不计输出），排序额外开销视实现而定。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);

        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) {
            minDiff = Math.min(minDiff, arr[i] - arr[i - 1]);
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            int diff = arr[i] - arr[i - 1];
            if (diff == minDiff) {
                List<Integer> pair = new ArrayList<>(2);
                pair.add(arr[i - 1]);
                pair.add(arr[i]);
                res.add(pair);
            }
        }
        return res;
    }
}

import "sort"

func minimumAbsDifference(arr []int) [][]int {
    sort.Ints(arr)

    minDiff := int(^uint(0) >> 1)
    for i := 1; i < len(arr); i++ {
        diff := arr[i] - arr[i-1]
        if diff < minDiff {
            minDiff = diff
        }
    }

    res := make([][]int, 0)
    for i := 1; i < len(arr); i++ {
        diff := arr[i] - arr[i-1]
        if diff == minDiff {
            res = append(res, []int{arr[i-1], arr[i]})
        }
    }
    return res
}

相似题目

题目	难度	考察点
532. 数组中的 k-diff 数对	中等	排序、双指针
462. 最少移动次数使数组元素相等 II	中等	排序
561. 数组拆分	简单	排序
976. 三角形的最大周长	简单	排序
628. 三个数的最大乘积	简单	排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/11580534