数据两两比较的高效算法?

Question

数据库有十万条数据，比较的规则是，第一条和第二条后面的所有数据进行比较，第二条和后第三条后面的所有数据进行比较，以此类推。。。比较所有的数据.不想使用多重循环,想在一个循环内全部搞定,请问有比较好的算法吗?

Answer 1

看到你的场景说是，找重复。
SELECT id from table GROUP BY id HAVING COUNT(*)>1
这样获取回来的就是含重复数据。

如果是如题所说的两两比较，如果限定 "两两比较" 必然是 O(n^2)，既然确定了时间复杂度，那么就不用算法效率了。剩下的就是考虑在那计算了。

如果数据规模不够大，内存里计算完全可以了，前提是数据规模不大。

详述场景～～～～～～～～～～～～～～～～

Answer 2

先排序,后比较
不建议在数据库中操作,最方便的就是把这10w 条数据取出来,放到 php 内存中来操作.

代码如下

$sql = "select id,data from table order by data asc";
$result =  [
     0=>     ['id'=>3, 'data'=>1],
     1=>     ['id'=>1, 'data'=>2],
     2=>     ['id'=>4, 'data'=>2],
     3=>     ['id'=>5, 'data'=>2],
     4=>     ['id'=>2, 'data'=>5],
];
//遍历小于
//小于当前元素下标的元素
//遍历大于
//大于当前元素下标的元素
//相同,有点复杂,代码如下
$same = array();
$current = 0;
$next = $current + 1;
//遍历一遍数组
while(isset($result[ $next ])) {
    $data = $result[ $current ][ 'data' ];
    //如果当前元素值和下一个元素值一样,放到值数组中
    if ($data == $result[ $next ][ 'data' ]) {
        $same[ $data ][] = $result[ $next ];
        $next ++;
    }else{  //如果不一样,当前元素指向  当下标为$next的元素
        $current = $next;
        $next = $current+1;
    }
}
var_export($same);
//结果
array (
  2 => 
  array (
    0 => 
    array (
      'id' => 4,
      'data' => 2,
    ),
    1 => 
    array (
      'id' => 5,
      'data' => 2,
    ),
  ),
)

Answer 3

有几个问题是需要注意的：
1，数据要在内存中做排序或对比，不要在数据库内执行；
2，两两比较的目的是什么？要从这10W+数据中取出最大的N个？还是做排序？建议在内存中用一个索引数组存储排序后的所有数据；
3，排序算法使用快排；

Answer 4

倒三角形算法就可以解决