时间戳

首页 > 解决方案 > 数组中的最大距离 | 竞争性编码问题

algorithm - 数组中的最大距离 | 竞争性编码问题

问题描述

问题陈述 -

给定 m 个数组，每个数组按升序排序。现在你可以从两个不同的数组中取出两个整数（每个数组选择一个）并计算距离。我们将两个整数 a 和 b 之间的距离定义为它们的绝对差 |ab|。你的任务是找到最大距离。

例子 -

Input: 
[[1,2,3],
 [4,5],
 [1,2,3]]
Output: 4

我的方法 - 由于数组已排序，因此在最终答案中，一个元素将来自数组的第一个索引，而另一个元素将来自数组的最后一个索引。因此，我能够设计一个蛮力解决方案，以得到答案。基本上我正在生成一个数组的最后一个元素和另一个数组的第一个元素的所有可能组合。这给了我 O(n^2) 的 TC。我怎样才能优化我的方法。?

标签： algorithmdata-structures

解决方案

这很简单。

  • 维护具有所有列表最小值的最小变量。
  • 在包括当前最小值之前，计算当前最小值与当前列表最大值的差异。
  • 从第一个到最后一个，从最后一个到第一个执行第 2 步。
  • 这样，您将考虑所有最小值和最大值的可能性，而无需为每一个生成或计算。

片段：

public int maxDistance(List<List<Integer>> arrays) {
        int max_diff = 0,min = arrays.get(0).get(0);
        
        for(int i=1;i<arrays.size();++i){
            List<Integer> curr = arrays.get(i);
            max_diff = Math.max(max_diff,Math.abs(curr.get(curr.size()-1) - min));
            min = Math.min(min,curr.get(0)); // take min afterwards
        }
        
        min = arrays.get(arrays.size()-1).get(0);
        
        for(int i=arrays.size()-2;i>=0;--i){
            List<Integer> curr = arrays.get(i);
            max_diff = Math.max(max_diff,Math.abs(curr.get(curr.size()-1) - min));
            min = Math.min(min,curr.get(0));  // take min afterwards
        }
        
        return max_diff;
    }
  • 时间复杂度：O(n)，空间复杂度：O(1)。

推荐阅读