寻找数组中的最小值与次小值：从排序到单次遍历的算法演进

2026-02-07 11:51:50 0条评论 2次阅读 0人点赞

在处理数组相关的编程问题时，寻找数组中的最小值是一个基础且常见的操作。然而，当我们需要更进一步，同时找到最小和第二小的元素时，事情就变得稍微有趣起来了。这不仅涉及到基本的遍历逻辑，还考验我们对边界条件的处理能力。

在这篇文章中，我们将深入探讨如何高效地解决这个问题。我们将从最直观的排序方法开始，分析其优缺点，进而过渡到更高效的线性扫描方法。我们将通过实际的代码示例（C++, Java, Python, C#）来演示如何实现这些算法，并讨论在实际开发中如何避免常见的陷阱。无论你是正在准备算法面试，还是希望在项目中优化代码性能，这篇文章都将为你提供实用的见解。

问题陈述

给定一个整数数组 arr[]，我们的目标是找到数组中最小和第二小的不重复元素。

核心要求：

  • 返回顺序：结果应按升序返回，即最小的元素在前，第二小的元素在后。
  • 边界情况：如果数组中所有元素都相同，或者数组元素个数少于两个，则意味着不存在有效的第二小元素，此时应返回 -1。

为了更直观地理解，让我们看几个例子：

示例 1：

> 输入： arr[] = {12, 25, 8, 55, 10, 33, 17, 11}

> 输出： [8, 10]

> 解释： 这里的 8 是全局最小值，而 10 是仅次于 8 的最小值。

示例 2：

> 输入： arr[] = {2, 4, 3, 5, 6}

> 输出： [2, 3]

> 解释： 2 是最小的，3 是第二小的。注意它们在数组中的位置并不影响结果。

示例 3：

> 输入： arr[] = {1, 1, 1}

> 输出： [-1]

> 解释： 所有元素都相同，虽然 1 是最小的，但我们找不到比它大或者不同的“第二小”元素。

—

方法一：使用排序 – 直观但非最优

思路解析：

当我们拿到这个问题时，最直接的想法往往是：“如果数组是有序的，问题不就解决了吗？” 确实如此。如果我们将数组按升序排序，最小的元素自然会位于数组的第一个位置（即索引 0）。

接下来，我们只需要从索引 1 开始遍历，寻找第一个不等于最小值的元素。一旦找到，那就是我们要找的第二小值。如果遍历结束仍未找到，说明所有元素都相等，返回 -1。

算法分析：

  • 时间复杂度： O(n × log(n))。这是由于排序算法（如快速排序、归并排序）的开销决定的。
  • 空间复杂度： O(1)（假设使用原地排序算法）。

虽然这种方法逻辑简单，但在大数据量下，排序的 O(n log n) 开销是不必要的。我们仅仅需要两个最小的数，却对整个数组进行了重排。不过，在某些对数据顺序有其他要求的场景下，这种方法依然有其价值。

代码实现：

在下面的代码中，我们展示了如何处理排序后的逻辑。请注意我们如何处理“所有元素相同”的边界情况。

// C++ 实现
#include 
#include 
#include 
#include 
using namespace std;

vector minAnd2ndMin(vector &arr) {
    
    // 步骤 1: 将数组按升序排序
    // sort 函数通常基于 IntroSort (混合了快速排序、堆排序和插入排序)
    sort(arr.begin(), arr.end());
    
    int n = arr.size();
    
    // 步骤 2: 初始化变量
    // 使用 INT_MIN 作为标记，表示尚未找到第二小的值
    int mini = arr[0]; 
    int secmini = INT_MIN;
    
    // 步骤 3: 遍历数组，寻找第一个大于 mini 的元素
    // 排序后，不同的元素必然聚集在一起
    for(int i = 1; i < n; i++) {
        
        // 一旦发现与最小值不同的元素，它就是第二小值
        if(arr[i] != mini) {
            secmini = arr[i];
            break; // 找到后立即退出循环，提高效率
        }
    }
    
    // 步骤 4: 检查是否找到了有效的第二小值
    if(secmini == INT_MIN) {
        return {-1}; // 说明所有元素都等于 mini
    }
    
    return {mini, secmini};
}

int main() {
    vector arr = {12, 25, 8, 55, 10, 33, 17, 11};
    vector res = minAnd2ndMin(arr);
    for(auto it : res) {
        cout << it << " ";
    }
    cout << endl;
    return 0;
}

// Java 实现
import java.util.ArrayList;
import java.util.Arrays;

class Solution {

    public static ArrayList minAnd2ndMin(int[] arr) {
        
        // 步骤 1: 利用 Java 工具类进行排序
        Arrays.sort(arr); 
        int n = arr.length;

        // 步骤 2: 获取最小值（排序后首元素）
        int mini = arr[0];
        int secmini = Integer.MIN_VALUE; 

        // 步骤 3: 寻找不同的元素
        for (int i = 1; i < n; i++) {
            
            if (arr[i] != mini) {
                secmini = arr[i];
                break;
            }
        }

        // 步骤 4: 构造返回结果
        if (secmini == Integer.MIN_VALUE) {
            ArrayList result = new ArrayList();
            result.add(-1);
            return result;
        }

        ArrayList result = new ArrayList();
        result.add(mini);
        result.add(secmini);
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {12, 25, 8, 55, 10, 33, 17, 11};
        ArrayList result = minAnd2ndMin(arr);
        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

# Python 实现
def minAnd2ndMin(arr):
    
    # 步骤 1: Python 内置的 sort() 方法非常高效且易读
    arr.sort()  
    
    # 步骤 2: 第一个元素即为最小值
    mini = arr[0]
    secmini = None # 使用 None 作为 Python 中的“未找到”标记

    # 步骤 3: 循环查找
    # 从索引 1 开始遍历
    for num in arr:
        if num != mini:
            secmini = num
            break

    # 步骤 4: 结果判断
    if secmini is None:
        return [-1]

    return [mini, secmini]

if __name__ == "__main__":
    arr = [12, 25, 8, 55, 10, 33, 17, 11]
    result = minAnd2ndMin(arr)
    print(*result)

// C# 实现
using System;
using System.Collections.Generic;

class Solution {
    
    public static List minAnd2ndMin(int[] arr) {
        
        // 步骤 1: Array.Sort 用于对数组进行原地排序
        Array.Sort(arr);
        int n = arr.Length;

        // 步骤 2: 初始化
        int mini = arr[0];
        int secmini = int.MinValue;

        // 步骤 3: 查找逻辑
        for (int i = 1; i < n; i++) {
            if (arr[i] != mini) {
                secmini = arr[i];
                break;
            }
        }

        // 步骤 4: 返回 List
        if (secmini == int.MinValue) {
            return new List { -1 };
        }

        return new List { mini, secmini };
    }

    public static void Main() {
        int[] arr = {12, 25, 8, 55, 10, 33, 17, 11};
        List result = minAnd2ndMin(arr);
        
        Console.WriteLine(string.Join(" ", result));
    }
}

—

方法二：单次遍历法 – 性能最优解

虽然排序法简单易懂，但它改变了数组的原始顺序（如果这很重要的话），且时间复杂度较高。作为追求极致性能的开发者，我们来看看更优的解法。

思路解析：

我们可以在一次遍历中同时找到最小值和第二小值。这就像是在赛跑中，我们需要记录第一名和第二名的成绩。

我们可以维护两个变量：

  • mini：存储当前找到的最小值。
  • sec_mini：存储当前找到的第二小值。

算法逻辑：

  • 初始化：首先，将 INLINECODEd5195063 和 INLINECODE6dcf959f 都初始化为一个非常大的数（例如 INLINECODE1c86e389 或 INLINECODE99dccdfe）。
  • 遍历数组：对于数组中的每一个元素 x：

* 如果 INLINECODE1d85fcca 小于 INLINECODE86de7e9c：

* 这说明我们发现了新的最小值。

* 此时，旧的 INLINECODE071ea000 就成了第二小的候选者（因为它是目前为止最小的，除了新的 INLINECODE9725c84a）。所以，先将 INLINECODE0aff7bad 赋值给 INLINECODEec806d9f。

* 然后，更新 mini = x。

* 否则，如果 INLINECODEc2fb5bc3 小于 INLINECODE0eaa4dd6 并且 INLINECODE02a57ce2 不等于 INLINECODE430b478e：

* 这说明 x 不是最小的，但它比我们当前记录的第二小值要小。

* 更新 sec_mini = x。

  • 最终检查：遍历结束后，如果 INLINECODE9887b5ad 仍然保持初始的大值（说明从未被更新过），则返回 INLINECODEe9df1343。否则返回 [mini, sec_mini]。

复杂度分析：

  • 时间复杂度： O(n)。我们只遍历了数组一次。
  • 空间复杂度： O(1)。只使用了两个额外的变量。

这是解决此类问题的标准线性时间算法，非常适合处理大规模数据。

代码实现：

// C++ 单次遍历实现
#include 
#include 
#include 
using namespace std;

vector minAnd2ndMin(vector &arr) {
    int n = arr.size();
    
    // 步骤 1: 初始化为最大可能值
    int mini = INT_MAX;
    int sec_mini = INT_MAX;

    // 步骤 2: 遍历数组
    for(int i = 0; i < n; i++) {
        // 情况 A: 发现了新的最小值
        if(arr[i] < mini) {
            sec_mini = mini; // 原来的最小值变成第二小值
            mini = arr[i];   // 更新最小值
        }
        // 情况 B: 当前元素介于最小和第二小之间，且不能等于最小值
        else if(arr[i] < sec_mini && arr[i] != mini) {
            sec_mini = arr[i];
        }
    }

    // 步骤 3: 检查结果有效性
    // 如果 sec_mini 还是 INT_MAX，说明从未更新过
    if(sec_mini == INT_MAX) {
        return {-1};
    }

    return {mini, sec_mini};
}

int main() {
    vector arr = {12, 25, 8, 55, 10, 33, 17, 11};
    vector res = minAnd2ndMin(arr);
    for(auto it : res) {
        cout << it << " ";
    }
    return 0;
}

// Java 单次遍历实现
import java.util.ArrayList;
import java.util.List;

class Solution {
    public static List minAnd2ndMin(int[] arr) {
        int n = arr.length;
        int mini = Integer.MAX_VALUE;
        int sec_mini = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            // 如果发现更小的值，更新最小值和第二小值
            if (arr[i] < mini) {
                sec_mini = mini;
                mini = arr[i];
            } 
            // 如果发现介于两者之间的值
            else if (arr[i] < sec_mini && arr[i] != mini) {
                sec_mini = arr[i];
            }
        }

        if (sec_mini == Integer.MAX_VALUE) {
            List res = new ArrayList();
            res.add(-1);
            return res;
        }

        List res = new ArrayList();
        res.add(mini);
        res.add(sec_mini);
        return res;
    }
}

# Python 单次遍历实现
def minAnd2ndMin(arr):
    
    # Python 中可以使用 float(‘inf‘) 表示无穷大
    mini = float(‘inf‘)
    sec_mini = float(‘inf‘)

    for x in arr:
        # 发现新的最小值
        if x < mini:
            sec_mini = mini
            mini = x
        # 发现新的第二小值
        elif x < sec_mini and x != mini:
            sec_mini = x

    if sec_mini == float('inf'):
        return [-1]

    return [mini, sec_mini]

常见陷阱与最佳实践

在实现上述算法时，作为开发者，我们需要注意一些常见的“坑”：

  • 重复值问题：

在方法二中，当我们更新 INLINECODE4dfb6b95 时，必须加上条件 INLINECODE35d115be。如果我们忽略了这一点，对于像 INLINECODE76c92303 这样的数组，算法可能会错误地返回 INLINECODEec7325d9 而不是 INLINECODE4c154411，因为第二个 INLINECODE845864b0 会满足“小于 INLINECODE8f8b716a”的条件（如果 INLINECODE6a74a722 初始化得当）。确保第二小的值必须是严格大于最小值的不同元素。

  • 数组长度不足：

在代码开始时，检查数组长度是否小于 2 是一个好的习惯，虽然我们的单次遍历逻辑也能处理这种情况（返回 -1），但显式检查可以避免不必要的计算。

  • 初始化的选择：

不要将 INLINECODE37033ce5 初始化为 0 或 -1。如果数组全是负数（例如 INLINECODE0dcff8ba），初始化为 0 会导致逻辑错误，因为 0 比所有负数都大，从而无法正确捕捉到第二小的负数。始终使用 INLINECODE4f798b22 或 INLINECODEe1b12d92 作为初始占位符。

实际应用场景

  • 数据清洗：在统计分析前，快速识别异常值或极值。
  • 比赛评分系统：确定谁是冠军和亚军，且需要处理并列第一的情况（此时没有亚军）。
  • 资源调度：寻找负载最低的两台服务器进行任务分配。

总结

在这篇文章中，我们探索了寻找数组中两个最小值的两种主要方法。

  • 排序法：代码简单，适合在不关心性能且数据量小的情况下使用，或者当你本身就需要对数组进行排序时。
  • 单次遍历法：性能卓越，时间复杂度为 O(n)，空间复杂度为 O(1)。这是生产环境中的首选方案，特别是在处理大规模数据流时。

掌握这些基础算法不仅有助于通过面试，更能让你在日常编程中对代码的效率有更深刻的理解。下次当你需要对数组进行极值查找时，不妨跳出简单的排序思维，尝试一下这种优雅的线性扫描方法吧！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/31818.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年