定义三元组(a, b, c)(其中a, b, c均为正数)的距离D=|a-b| + |b-c| + |c-a|。给定三个非空整数集合S1、S2和S3,按升序分别存储在3个数组中。设计一个尽可能高效的算法,计算并输出所有可能的三元组(a, b, c)(a∈S1, b∈S2, c∈S3)中的最小距离。要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用 C 或 C++语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。
二、解答(1)通过三个队列每次出队最小值的策略; (2)C++实现:
// -*- coding: utf-8 -*-// @ Date: 2021/5/20 13:14// @ Author : RichardLau_Cx// @ file: Richard.cpp// @ IDE: Dev-C++// @ Source : Data_Structure#include #include #include using namespace std; int minimum(int a, int b, int c){ // 返回三个值中最小的那个值 if (a