给定n
一个n
正整数数组,需要有多少种方法可以选择三个数字以使它们不能形成三角形。
例子:
3
4 2 10
回答:
1
我的方法(在JAVA
)
int[] arr = new int[n];//list of the numbers given
int count=0;//count of all such triplets
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
Arrays.sort(arr);
for(int i=n-1;i>=0;i--)
{
int j=0;
int k= i-1;
while(j<k && k>=0)
{
if(arr[i]>=arr[j]+arr[k])//condition for no triangle formation
{
count++;
j++;//checking the next possible triplet by varying the third number
}
else if(arr[i]<arr[j]+arr[k])
{
j=0;
k--;//now varying the second number if no such third number exists
}
}
}
System.out.println(count);
我的算法:
在对列表进行排序后,我试图找到小于 的所有数字,在arr[i]
这种arr[i]>=arr[j]+arr[k]
情况下,不会形成三角形。
但我正在接受timed-out
这个解决方案。任何人都可以提出更好的方法来解决这个问题吗?