Java顺序查找知识点（含面试大厂题和源码）

顺序查找（Sequential Search），也称为线性查找，是一种简单直观的查找算法。它通过逐个检查数据集中的每个元素来查找目标值。顺序查找不要求数据集是有序的，因此它适用于任何形式的数据集，包括数组、链表、列表等。

顺序查找的工作原理：

1. 开始查找：从数据集的起始位置开始。
2. 逐个比较：将目标值与当前位置的元素进行比较。
3. 匹配或继续：如果目标值与当前元素相等，则查找成功；如果不相等，移动到下一个位置继续比较。
4. 到达终点：如果遍历完整个数据集都没有找到目标值，则查找失败。

顺序查找的优缺点：

优点：

• 简单易实现：顺序查找的算法逻辑非常简单，易于理解和实现。
• 不要求有序：不需要数据集事先排序，适用于任何无序的数据集。

缺点：

• 效率较低：在最坏的情况下，顺序查找需要遍历整个数据集才能找到目标值或确定目标值不存在，因此时间复杂度为 O(n)。
• 空间复杂度：顺序查找不需要额外的存储空间，空间复杂度为 O(1)。

顺序查找的Java实现：

public class SequentialSearch {
    public int sequentialSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i; // 返回目标值的索引
            }
        }
        return -1; // 如果没有找到，返回-1
    }

    public static void main(String[] args) {
        SequentialSearch search = new SequentialSearch();
        int[] array = {3, 5, 7, 9, 11};
        int target = 9;
        int result = search.sequentialSearch(array, target);
        System.out.println("Index of " + target + " is: " + result);
    }
}

在面试中，了解顺序查找的原理和实现是非常重要的，尤其是当面试官询问如何处理无序数据集的查找问题时。顺序查找是最基本的查找方法，也是学习更高级查找算法（如二分查找、哈希查找等）的基础。

题目 1：找出数组中缺失的最小正整数

描述：
给定一个包含 n 个正整数的数组，其中 n 也是正整数。数组中的数唯一且在 1 到 n 之间，但可能不是连续的。找出所有数中缺失的最小正整数。

示例：

输入: [2, 3, 4, 6, 7, 9, 12]
输出: 5

Java 源码：

public class FindMissingPositive {
    public int findMissingPositive(int[] nums) {
        boolean[] marked = new boolean[nums.length + 1];
        for (int num : nums) {
            if (num <= nums.length && marked[num] == false) {
                marked[num] = true;
            }
        }
        for (int i = 1; i <= nums.length; i++) {
            if (!marked[i]) {
                return i;
            }
        }
        return -1; // 如果没有找到，返回-1
    }

    public static void main(String[] args) {
        FindMissingPositive solution = new FindMissingPositive();
        int[] nums = {2, 3, 4, 6, 7, 9, 12};
        int result = solution.findMissingPositive(nums);
        System.out.println("The missing positive number is: " + result);
    }
}

题目 2：存在重复元素 II

描述：
给定一个整数数组和一个整数 k，找出数组中和为 k 的一对数字。你可以假设每对数字 (i, j) 都是唯一的，并且每对数字 (i, j) 最多只能使用一次。

示例：

输入: nums = [2, 3, 4, 6, 7, 9, 12], k = 10
输出: [3, 7]

Java 源码：

public class FindSumPairs {
    public List<List<Integer>> findSumPairs(int[] nums, int k) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == k) {
                    result.add(Arrays.asList(nums[i], nums[j]));
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        FindSumPairs solution = new FindSumPairs();
        int[] nums = {2, 3, 4, 6, 7, 9, 12};
        int k = 10;
        List<List<Integer>> result = solution.findSumPairs(nums, k);
        System.out.println("The pairs with sum " + k + " are: " + result);
    }
}

题目 3：字符串中的第一个唯一字符

描述：
给定一个字符串，找到字符串中第一个不重复的字符。

示例：

输入: "leetcode"
输出: "e"

Java 源码：

public class FirstUniqueChar {
    public String firstUniqChar(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        for (char c : s.toCharArray()) {
            if (count[c - 'a'] == 1) {
                return String.valueOf(c);
            }
        }
        return "";
    }

    public static void main(String[] args) {
        FirstUniqueChar solution = new FirstUniqueChar();
        String s = "leetcode";
        String result = solution.firstUniqChar(s);
        System.out.println("The first unique character is: " + result);
    }
}

这些题目和源码展示了顺序查找在解决实际问题中的应用。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！