热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

检查数组中的最小元素是否小于或等于每隔一个元素的一半

检查数组中的最小元素是否小于或等于每隔一个元素的一半原文:htt

检查数组中的最小元素是否小于或等于每隔一个元素的一半

原文:https://www . geesforgeks . org/check-如果数组中的最小元素小于或等于其他元素的一半/

给定一个数组 arr[] ,任务是检查数组中的最小元素是否小于或等于其他元素的一半。如果是,则打印“是”,否则打印“否”。
注:给定数组中的最小数总是唯一的。

示例:

输入: arr = {2,1,4,5}
输出:
解释:
1 是 arr[]数组中的最小元素,2,4,5 除以 2 得到 1,2,2.5,大于或等于最小数。因此,打印“是”。

输入: arr = {2,4,5,3}
输出:
解释:
2 是 arr[]数组中的最小元素,4,5,3 除以 2 得到 2,2.5,1.5,其中整数 3 不返回大于或等于最小数的值(1.5 <2)。因此,打印“否”。

方法 1:
要解决上面提到的问题,我们必须借助循环找到最小元素,然后再次扫描整个数组,检查两次最小元素是否小于或等于每隔一个元素。但是这个解决方案使用两个循环花费了 O(N)个时间,并且可以在只涉及一次迭代的情况下进一步优化。

方法 2:
为了优化上述解,我们可以在单次迭代中找到最小的以及第二小的元素本身。然后简单地检查最小元素的两倍是否小于或等于第二小元素。

下面是上述方法的实现:

C++


// C++ implementation to Check if the minimum element in the
// array is greater than or equal to half of every other elements
#include <bits/stdc++.h>
using namespace std;
// Function to Check if the minimum element in the array is
// greater than or equal to half of every other element
void checkMin(int arr[], int len)
{
    // Initialise the variables to store
    // smallest and second smallest
    int smallest = INT_MAX, secondSmallest = INT_MAX;
    for (int i = 0; i < len; i++) {
        // Check if current element is smaller than smallest,
        // the current smallest will become secondSmallest
        // and current element will be the new smallest
        if (arr[i] < smallest) {
            secondSmallest = smallest;
            smallest = arr[i];
        }
        // Check if current element is smaller than
        // secondSmallest simply update the latter
        else if (arr[i] < secondSmallest) {
            secondSmallest = arr[i];
        }
    }
    if (2 * smallest <= secondSmallest)
        cout << "Yes";
    else
        cout << "No";
}
// Driver code
int main()
{
    int arr[] = { 2, 3, 4, 5 };
    int len = sizeof(arr) / sizeof(arr[0]);
    checkMin(arr, len);
}


Java 语言(一种计算机语言,尤用于创建网站)


// Java implementation to check
// if the minimum element in the
// array is greater than or equal
// to half of every other elements
import java.util.*;
class GFG{
// Function to Check if the minimum
// element in the array is greater
// than or equal to half of every
// other elements
static void checkMin(int arr[], int len)
{
    // Initialise the variables to store
    // smallest and second smallest
    int smallest = Integer.MAX_VALUE;
    int secondSmallest = Integer.MAX_VALUE;
    for(int i = 0; i < len; i++)
    {
       // Check if current element is smaller than 
       // smallest, the current smallest will 
       // become secondSmallest and current 
       // element will be the new smallest
       if (arr[i] < smallest)
       {
           secondSmallest = smallest;
           smallest = arr[i];
       }
       // Check if current element is smaller than
       // secondSmallest simply update the latter
       else if (arr[i] < secondSmallest)
       {
           secondSmallest = arr[i];
       }
    }
    if (2 * smallest <= secondSmallest)
        System.out.print("Yes");
    else
        System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 3, 4, 5 };
    int len = arr.length;
    checkMin(arr, len);
}
}
// This code is contributed by amal kumar choubey


Python 3


# Python3 implementation to Check if
# the minimum element in the array
# is greater than or equal to half
# of every other element
import math
# Function to Check if the minimum element
# in the array is greater than or equal to
# half of every other element
def checkMin(arr, n):
    # Initialise the variables to store
    # smallest and second smallest
    smallest = math.inf
    secondSmallest = math.inf
    for i in range(n):
        # Check if current element is
        # smaller than smallest,
        # the current smallest will become
        # secondSmallest and current element
        # will be the new smallest
        if(arr[i] < smallest):
            secondSmallest = smallest
            smallest = arr[i]
        # Check if current element is smaller than
        # secondSmallest simply update the latter
        elif(arr[i] < secondSmallest):
            secondSmallest = arr[i]
    if(2 * smallest <= secondSmallest):
        print("Yes")
    else:
        print("No")
# Driver code
if __name__ == '__main__':
    arr = [ 2, 3, 4, 5 ]
    n = len(arr)
    checkMin(arr, n)
# This code is contributed by Shivam Singh.


C


// C# implementation to check
// if the minimum element in the
// array is greater than or equal
// to half of every other elements
using System;
class GFG{
// Function to Check if the minimum
// element in the array is greater
// than or equal to half of every
// other elements
static void checkMin(int []arr, int len)
{
    // Initialise the variables to store
    // smallest and second smallest
    int smallest = int.MaxValue;
    int secondSmallest = int.MaxValue;
    for(int i = 0; i < len; i++)
    {
       // Check if current element is smaller than
       // smallest, the current smallest will
       // become secondSmallest and current
       // element will be the new smallest
       if (arr[i] < smallest)
       {
           secondSmallest = smallest;
           smallest = arr[i];
       }
       // Check if current element is smaller than
       // secondSmallest simply update the latter
       else if (arr[i] < secondSmallest)
       {
           secondSmallest = arr[i];
       }
    }
    if (2 * smallest <= secondSmallest)
        Console.Write("Yes");
    else
        Console.Write("No");
}
// Driver code
public static void Main(String[] args)
{
    int []arr = { 2, 3, 4, 5 };
    int len = arr.Length;
    checkMin(arr, len);
}
}
// This code is contributed by amal kumar choubey


java 描述语言


<script>
// Javascript implementation to check 
// if the minimum element in the
// array is greater than or equal
// to half of every other elements
// Function to Check if the minimum
// element in the array is greater
// than or equal to half of every
// other element
function checkMin(arr, len)
{
    // Initialise the variables to store
    // smallest and second smallest
    var smallest = Number.INFINITY,
        secondSmallest = Number.INFINITY;
    for(var i = 0; i < len; i++)
    {
        // Check if current element is
        // smaller than smallest, the
        // current smallest will become
        // secondSmallest and current
        // element will be the new smallest
        if (arr[i] < smallest)
        {
            secondSmallest = smallest;
            smallest = arr[i];
        }
        // Check if current element is smaller than
        // secondSmallest simply update the latter
        else if (arr[i] < secondSmallest)
        {
            secondSmallest = arr[i];
        }
    }
    if (2 * smallest <= secondSmallest)
        document.write("Yes");
    else
        document.write("No");
}
// Driver code
var arr = [ 2, 3, 4, 5 ];
var len = 4;
checkMin(arr, len);
// This code is contributed by akshitsaxenaa09
script>

Output: 

No

时间复杂度: O(N),其中 N 为给定数组的长度。
辅助空间: O(N)。


推荐阅读
  • 本文介绍了使用Java实现大数乘法的分治算法,包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]
  • Java容器中的compareto方法排序原理解析
    本文从源码解析Java容器中的compareto方法的排序原理,讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点,回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录,展示了整个讲解过程。 ... [详细]
  • 本文介绍了如何在给定的有序字符序列中插入新字符,并保持序列的有序性。通过示例代码演示了插入过程,以及插入后的字符序列。 ... [详细]
  • 本文详细介绍了Java中vector的使用方法和相关知识,包括vector类的功能、构造方法和使用注意事项。通过使用vector类,可以方便地实现动态数组的功能,并且可以随意插入不同类型的对象,进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下,使用vector类是一个很好的选择。 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • Java太阳系小游戏分析和源码详解
    本文介绍了一个基于Java的太阳系小游戏的分析和源码详解。通过对面向对象的知识的学习和实践,作者实现了太阳系各行星绕太阳转的效果。文章详细介绍了游戏的设计思路和源码结构,包括工具类、常量、图片加载、面板等。通过这个小游戏的制作,读者可以巩固和应用所学的知识,如类的继承、方法的重载与重写、多态和封装等。 ... [详细]
  • Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]
  • 本文介绍了一个Java猜拳小游戏的代码,通过使用Scanner类获取用户输入的拳的数字,并随机生成计算机的拳,然后判断胜负。该游戏可以选择剪刀、石头、布三种拳,通过比较两者的拳来决定胜负。 ... [详细]
  • 本文讨论了如何优化解决hdu 1003 java题目的动态规划方法,通过分析加法规则和最大和的性质,提出了一种优化的思路。具体方法是,当从1加到n为负时,即sum(1,n)sum(n,s),可以继续加法计算。同时,还考虑了两种特殊情况:都是负数的情况和有0的情况。最后,通过使用Scanner类来获取输入数据。 ... [详细]
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • 本文讨论了一个关于cuowu类的问题,作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案,并给出了两个可能导致错误的原因。 ... [详细]
  • C# 7.0 新特性:基于Tuple的“多”返回值方法
    本文介绍了C# 7.0中基于Tuple的“多”返回值方法的使用。通过对C# 6.0及更早版本的做法进行回顾,提出了问题:如何使一个方法可返回多个返回值。然后详细介绍了C# 7.0中使用Tuple的写法,并给出了示例代码。最后,总结了该新特性的优点。 ... [详细]
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • 动态规划算法的基本步骤及最长递增子序列问题详解
    本文详细介绍了动态规划算法的基本步骤,包括划分阶段、选择状态、决策和状态转移方程,并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中,在以后尽可能多地利用这些子问题的解,从而提高算法的效率。 ... [详细]
  • 猜字母游戏
    猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]
author-avatar
大帅哥明日夜
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有