是否有可能在 O(n) 时间内找到差异最小的两个数字 [英] Is it possible to find two numbers whose difference is minimum in O(n) time

问题描述

给定一个未排序的整数数组，并且不做任何假设数组中的数字:
能不能找出两个数O(n) 时间的差异最小?

Given an unsorted integer array, and without making any assumptions on the numbers in the array:
Is it possible to find two numbers whose difference is minimum in O(n) time?

两个数 a、b 的差定义为 abs(a-b)

Difference between two numbers a, b is defined as abs(a-b)

推荐答案

查找列表中最小和最大的元素.最小-最大的差异将是最小的.

Find smallest and largest element in the list. The difference smallest-largest will be minimum.

如果您正在寻找非负差异，那么这当然至少与检查数组是否有两个相同的元素一样困难.这称为元素唯一性问题并且没有任何额外的假设(例如限制整数的大小，允许其他操作比比较)需要 >= n log n 时间.这是找到最近点对的一维情况.

If you're looking for nonnegative difference, then this is of course at least as hard as checking if the array has two same elements. This is called element uniqueness problem and without any additional assumptions (like limiting size of integers, allowing other operations than comparison) requires >= n log n time. It is the 1-dimensional case of finding the closest pair of points.

这篇关于是否有可能在 O(n) 时间内找到差异最小的两个数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！