如何从蛮力算法转向智能算法?

Question

当我解决问题时，我总是使用蛮力来算法，这些算法总是给出时间限制问题。 我真的不知道该怎么办？ 如何将我的方法从蛮力算法更改为智能算法

例如，我正在解决hackerrank上的这个问题：

"考虑一个整数数组，.我们将两个元素之间的绝对差和(其中)定义为 的绝对值。

给定一个整数数组，查找并打印数组中任意两个元素之间的最小绝对差值。

输入格式

第一行包含一个整数，表示(整数的数量)。 第二行包含以空格分隔的整数，用于描述 的相应值。

约束

2<n<2^5
10^-9<ai<10^9

输出格式
打印数组中任意两个元素之间的最小绝对差值。

示例输入

3
3 -7 0

示例输出

3

我的方法是用每个元素减去每个元素
并打印最小差异，但它给出了时间限制问题

Answer 1

1. 按升序对数组进行排序。

2. 现在检查每两个连续元素之间的差异并最小化差异。

   Arrays.sort(arr);
   int minDiff = arr[n - 1] - arr[0];
   for (int i = 0; i < n - 1; i++) {
   int tmpDiff = arr[i + 1] - arr[i];
   if (tmpDiff < minDiff) {
   minDiff = tmpDiff;
   }
   }
   

简单的观察是 - 当数组被排序时，对于任何元素arr[i]，立即更小和更大的元素将分别停留在左边(i - 1个位置)和右边(i + 1个位置)。不可能用arr[i - 1]或arr[i + 1]以外的元素获得更小的绝对差值。(为什么？

这是一个简单的贪婪问题。你必须多练习才能想出解决这个问题的想法。在提出任何想法之后，尝试通过矛盾证明，通过归纳证明来验证正确性。祝你好运！

编辑

排序将花费O(nlogn)，并产生一些字符串比较开销。迭代以找到差异将需要O(n).因此，时间复杂度总体上将O(nlog n)。

您的想法需要O(n^2)，因为您将每个元素与每个元素进行比较时要慢得多。

Answer 2

强制意味着您需要执行所有可能的解决方案集，以验证您的问题是否已解决。

为了避免做一个粗暴的力量，你需要找到一种方法来减少可能的解决方案集，以便尝试更少的解决方案。