最大の境界三角形リートコードソリューション


難易度 簡単に
よく聞かれる C3 IoT
数学 並べ替え(ソート)

問題文

問題の中で」最大 周囲 Triangle」には、n個の値を持つ配列が与えられます。 すべての値は正の整数です。 質問は、これらの値から構築できる三角形の最大周囲長を見つけるように依頼します。 三角形を作成できない場合は、0を出力する必要があります。

arr = [3,2,3,4]
10

説明: これらの値を使用して形成できる三角形の最大周囲長は10で、三角形の辺は4,3,3、XNUMX、XNUMXです。

最大の境界三角形リートコードソリューションのアプローチ

これは基本的な数学の問題です。 したがって、それを解決するには、三角形では任意のXNUMXつの辺の長さの合計が常にXNUMX番目の辺よりも大きいというこの定理を知っている必要があります。 そうでなければ、それらは三角形を形成しません。 三角形の辺が a、b、およびc。 画像は、この定理を満たさない場合、三角形を作成できないことを示しています。

最大の周囲三角形に対するリートコードソリューション

質問が最大の周囲の三角形を見つけるように求めているので、a + b> c、b + c> a、およびa + c> bの条件を満たすすべての可能なトリプレットから、a +がb + cが最大です。

したがって、最大の周囲長を取得するには、a、b、およびcの値をできるだけ大きくする必要があります。 配列を並べ替えてから、定理を満たす場合は最大のXNUMXつの値から始めます。 もしそうなら、それらの合計は必要な値です。 それ以外の場合は、次に大きいXNUMXつの値を確認します。

そのようなトリプレットが存在しない場合、三角形の最大の周囲長は0です。

 製品の導入

最大の周囲三角形のC ++コード

#include <bits/stdc++.h> 
using namespace std; 
    int largestPerimeter(vector<int>&  arr) {
        int n=arr.size();
        sort(arr.begin(),arr.end());
       for (int i =n - 1; i > 1; --i)
            if (arr[i] < arr[i - 1] + arr[i - 2])
                return arr[i] + arr[i - 1] + arr[i - 2];
        return 0;
    }
int main() 
{ 
 vector<int> arr = { 3,2,3,4 }; 
 cout<<largestPerimeter(arr)<<endl; 
 return 0;
}
10

最大周長三角形のJavaコード

import java.util.Arrays; 
public class Tutorialcup {
    public static int largestPerimeter(int[] arr) {
        Arrays.sort(arr);
        int n= arr.length;
        for (int i =n - 1; i > 1; --i)
            if (arr[i] < arr[i - 1] + arr[i - 2])
                return arr[i] + arr[i - 1] + arr[i - 2];
        return 0;
    }
  public static void main(String[] args) {
    int [] arr = {3,2,3,4}; 
    int ans= largestPerimeter(arr);
    System.out.println(ans);
  }
}

 

10

最大の周辺三角形リートコードソリューションの複雑さの分析

時間の複雑さ

上記のコードの時間計算量は O(nlogn) 配列をソートしているからです。 ここで、nは配列のサイズです。

スペースの複雑さ

上記のコードのスペースの複雑さは O(1) 答えを格納するために変数のみを使用しているためです。

リファレンス