暴力解法

暴力法

我们讨论算法时，可以从最直接、最全面的方法开始——暴力法解决一个问题。这种方法要求我们遍历所有可能的解决方案来找到问题的答案。例如，如果我们有一个整数数组，并希望找出其中的最小值、最大值或某个特定元素，那么暴力法就需要遍历数组中的每一个元素，以找到目标元素。在这个阶段，没有任何捷径可走，也没有性能上的优化。

尽管这种解题方式是最低效的，但它往往是人们最先想到的方法。此外，暴力法的一个优点是：只要问题存在解，我们一定能通过这种方式找到它。一旦有了基本的解决思路，就可以专注于如何让解决方案变得更高效。

带着这个思路，让我们通过一个例子来帮助你直观理解这一方法。

线性查找

线性查找（也称顺序查找）是一种在给定数组中寻找目标值的方法。它依次检查数组中的每个元素，直到找到目标值或遍历完所有元素为止。线性查找在最坏情况下时间复杂度为线性时间，最多需要进行 n 次比较，其中 n 是列表的长度。

假设我们得到如下一个无序的整数数组：

现在，我们可以被要求在数组中查找一个特定元素并返回其索引。这个元素可以是任意指定的整数值，也可以是数组中的最大值或最小值。

假设我们需要找出数组中的最大值，使用暴力穷举搜索技术，其查找过程如下：

以下代码展示了该方法的实现：

Max

1class Maximum {
2    public static int maximum_index(int array[], int array_size) {
3        int max_index = 0; // 初始化索引为0
4        int max_val = Integer.MIN_VALUE; // 将最大值设为最小可能值
5        for (int i = 0; i < array_size; i++) // 遍历数组中的每个元素
6        {
7            if (max_val < array[i]) {
8                max_val = array[i];
9                max_index = i;
10            }
11        }
12        return max_index;
13    }
14
15    public static void main(String args[]) {
16        int array_size = 9;
17        int nums[] = {2,4,6,3,5,7,9,1,8};
18        int max_index = maximum_index(nums, array_size);
19
20        System.out.println("最大值 " + nums[max_index] + " 位于索引 " + max_index);
21    }
22}

FindNum

1class Find {
2    public static int find_index(int array[], int to_find, int array_size) // 接收一个整数数组和要查找的数值，返回元素索引，若不存在则返回-1
3    {
4        for (int i = 0; i < array_size; i++) // 遍历数组中的每个元素
5        {
6            if (array[i] == to_find) // 判断当前元素是否为目标值
7            {
8                return i; // 找到则返回其索引
9            }
10        }
11        return -1; // 未找到，返回-1
12    }
13
14    public static void main(String args[]) {
15        int number_to_search = 7;
16        int array_size = 9;
17        int nums[] = {2,4,6,3,5,7,9,1,8};
18        int index_found = find_index(nums, number_to_search, array_size);
19
20        if (index_found != -1)
21            System.out.println("数字 " + number_to_search + " 在索引 " + index_found + " 处找到");
22
23        else
24            System.out.println("数字 " + number_to_search + " 未找到");
25    }
26}

Min

1class Minimum {
2    public static int minimum_index(int array[], int array_size) {
3        int min_index = 0; // 初始化索引为0
4        int min_val = Integer.MAX_VALUE; // 将最小值设为最大可能值
5        for (int i = 0; i < array_size; i++) // 遍历数组中的每个元素
6        {
7            if (min_val > array[i]) {
8                min_val = array[i];
9                min_index = i;
10            }
11        }
12        return min_index;
13    }
14
15    public static void main(String args[]) {
16        int array_size = 9;
17        int nums[] = {2,4,6,3,5,7,9,1,8};
18        int min_index = minimum_index(nums, array_size);
19
20        System.out.println("最小值 " + nums[min_index] + " 位于索引 " + min_index);
21    }
22}

时间复杂度： $O(n)$ —— 因为在最坏情况下，我们只需对每个元素检查一次。