【算法题解】9. 邻值查找

╰半夏微凉° 2024-03-29 15:07 37阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解题思路
     *  代码实现
     *  复杂度分析

> 这是一道中等难度的题。  
> 题目来自：[AcWing][]

### 题目 ###

给定一个长度为 `n` 的序列 `A`，`A`中的数各不相同。

对于 `A` 中的每一个数 `Ai`，求：  
`min|Ai−Aj|`，其中 `1 <= j < i`。

以及令上式取到最小值的 `j`（记为 `Pi`）。若最小值点不唯一，则选择使 `Aj`较小的那个。

**输入格式**  
第一行输入整数 `n`，代表序列长度。  
第二行输入 `n` 个整数 `A1 … An`, 代表序列的具体数值，数值之间用空格隔开。

**输出格式**  
输出共 `n−1` 行，每行输出两个整数，数值之间用空格隔开。  
分别表示当 `i` 取 `2∼n` 时，对应的 `min|Ai−Aj|` 和 `Pi`的值。

**数据范围**  
`n <= 10^5`  
`|Ai| <=10^9`

**输入样例：**

3
    1 5 3

**输出样例：**

4 1
    2 1

### 解题思路 ###

首先排除暴力解法，毫无疑问会超时。如果不暴力循环，那么怎么可以获取到位置在 `Ai` 前面且与 `Ai` 差值最小的数呢？

既然是求差值最小，那么有一个思路就是可以将序列中的所有数按照从小到大排序，那么与`Ai`差值最小的数肯定就是排序后`Ai`的前一后数或者后一个数。但是按正常从前往后找的时候，我们无法确定这两个数排序前是否是在 `Ai` 的前面。

这时候可以考虑倒序去找，即先找最后一个 `An` 的答案，因为对于最后一个数来说，其他数肯定都在它的前面。当得到最后一个数的答案后，直接将 `An` 从排序后的序列中删除，然后再求 `A(n-1)` 的答案，这个时候序列中的其它数排序前肯定都在`A(n-1)`前面，因为在它后面的数都已经被删掉了，以此类推，直到得到 `A2` 的答案。

**值得注意的是：**

1.  解法中需要多次删除序列中的数，所以我们应该使用链表来存储排序序列。
2.  题目要求输出差值最小的数的位置，所以我们还需要记录每个数的初始位置。

以输入 `1 3 5 2 4` 为例：  
![【算法题解】9. 邻值查找][9.]

### 代码实现 ###

import java.util.Arrays;
    import java.util.Comparator;
    import java.util.Scanner;
    
    public class Main {
        
    
        public static void main(String[] args) {
        
            Scanner input = new Scanner(System.in);
    
            int n = input.nextInt();
    
            int[] nums = new int[n + 1];
            //存放下标，
            Integer[] rank = new Integer[n + 1];
            for (int i = 1; i <= n; i++) {
        
                nums[i] = input.nextInt();
                rank[i] = i;
            }
    
            Arrays.sort(rank, 1, n + 1, Comparator.comparingInt(r -> nums[r]));
    
            ListNode protect = new ListNode(0, 0);
            ListNode[] nodes = new ListNode[n + 1];
            ListNode latestNode = protect;
            for (int i = 1; i <= n; i++) {
        
                int index = rank[i];
                int num = nums[index];
                ListNode node = new ListNode(num, index);
                node.pre = latestNode;
                latestNode.next = node;
                nodes[index] = node;
                latestNode = node;
            }
    
            // 删除保护节点
            protect.next.pre = null;
    
            int[][] ans = new int[n + 1][2];
            //倒叙计算结果
            for(int i = n; i >= 2; i--){
        
                ListNode node = nodes[i];
                ans[i] = calMin(node);
                //删掉当前节点
                deleteCurNode(node);
    
            }
    
            for (int i = 2; i <= n; i++) {
        
                System.out.println(ans[i][0] + " " + ans[i][1]);
            }
    
        }
    
        private static void deleteCurNode(ListNode node) {
        
            if(node.pre != null){
        
                node.pre.next = node.next;
            }
            if(node.next != null){
        
                node.next.pre = node.pre;
            }
        }
    
        // 返回一个数组min，min[0]=|Ai−Aj|，min[1] = Pi
        static int[] calMin(ListNode node){
        
            int[] min = new int[2];
            ListNode pre = node.pre;
            if(pre != null){
        
                min[0] = Math.abs(node.num - pre.num);
                min[1] = pre.index;
            }
            ListNode next = node.next;
            if(next != null){
        
                int diff = Math.abs(node.num - next.num);
                if(pre == null || diff < min[0] || diff == min[0] && next.num < pre.num){
        
                    min[0] = diff;
                    min[1] = next.index;
                }
            }
            return min;
        }
    
        static class ListNode{
        
            private int num;
            private int index;
            private ListNode next;
            private ListNode pre;
    
            public ListNode(int num, int index) {
        
               this.num = num;
               this.index = index;
            }
    
            public ListNode getNext() {
        
                return next;
            }
    
            public void setNext(ListNode next) {
        
                this.next = next;
            }
    
            public ListNode getPre() {
        
                return pre;
            }
    
            public void setPre(ListNode pre) {
        
                this.pre = pre;
            }
        }
    
    }

### 复杂度分析 ###

时间复杂度  O ( N ∗ l o g N ) O(N \* logN) O(N∗logN)：算法中所有的循环时间复杂度均为 O ( N ) O(N) O(N)，而数组排序的时间复杂度是 O ( N ∗ l o g N ) O(N \* logN) O(N∗logN)，所以总的来说时间复杂度为 O ( N ∗ l o g N ) O(N \* logN) O(N∗logN)。

空间复杂度 O ( N ) O(N) O(N)：算法中所有存储变量空间复杂度都是 O ( N ) O(N) O(N)。

[AcWing]: https://www.acwing.com/problem/content/description/138/
[9.]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/6ede42313bc94948976c7e21c8c8440e.png