时间戳

首页 > 解决方案 > 给定一个整数数组，如何找到最大数的所有公倍数？

c# - 给定一个整数数组，如何找到最大数的所有公倍数？

问题描述

这是我在这个网站上的第一个问题。我正在练习 Hackerrank 上的一个问题，该问题要求找到“两套之间”的数字。给定两个整数数组，我必须找到符合以下两个条件的数字：1）第一个数组中的元素必须都是数字的因数 2）数字必须是所有数的因数第二个数组的元素

我知道我需要找到第一个数组中每个元素的所有公倍数，但这些倍数需要小于或等于第二个数组的最小值。我首先对第一个数组进行排序，然后在第一个数组中找到仅最大数的所有倍数（同样，直到第二个数组的最小值的最大值）并将这些倍数存储在一个列表中。然后，我移动到第一个数组中的第二大元素，并针对现有倍数数组对其进行测试。现有倍数列表中不是第一个数组的第二大元素的倍数的所有元素都将被删除。然后我测试第一个数组的第三个最大值，一直到最小值。当我按降序遍历第一个数组时，应该修剪现有倍数的列表。我' 我编写了一个解决方案，该解决方案仅通过了站点上 9 个测试用例中的 5 个，请参见下面的代码。我的任务是编辑 getTotalX 函数，我自己创建了 getCommonMultiples 函数作为助手。我没有创建或编辑主要功能。我不确定为什么我没有通过其他 4 个测试用例，因为我看不到任何测试用例是什么。

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    /*
     * Complete the getTotalX function below.
     */
    static int getTotalX(int[] a, int[] b) {
        //get minimum value of second array
        int b_min = b.Min();

        //create List to hold multiples
        List<int> multiples = getCommonMultiples(a, b_min);

        //create List to hold number of ints which are in solution
        List<int> solutions = new List<int>();
        foreach(int x in multiples)
        {
            foreach(int y in b)
            {
                if (y % x == 0 && !solutions.Contains(x))
                {
                    solutions.Add(x);
                }
                else
                {
                    break;
                }
            }
        }
        return solutions.Count;
    }

    static List<int> getCommonMultiples(int[] array, int max)
    {
        //make sure array is sorted
        Array.Sort(array);
        int x = array.Length - 1; //x will be the last # in array -- the max
        int y = 1;
        //find all multiples of largest number first and store in a list
        int z = array[x] * y;
        List<int> commonMultiples = new List<int>();
        while(z <= max)
        {
            commonMultiples.Add(z);
            y++;
            z = array[x] * y;
        } 

        //all multiples of largest number are now added to the list
        //go through the smaller numbers in query array
        //only keep elements in list if they are also multiples of smaller 
        //numbers

        int xx = array.Length - 2;
        for(int a = array[xx]; xx >= 0; xx--)
        {
            foreach(int b in commonMultiples.ToList())
            {
                if (b % a != 0)
                {
                    commonMultiples.Remove(b);
                }
                else
                {
                    continue;
                }
            }
        }
        return commonMultiples;
    }

    static void Main(string[] args) {
        TextWriter tw = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nm = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nm[0]);

        int m = Convert.ToInt32(nm[1]);

        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp))
        ;

        int[] b = Array.ConvertAll(Console.ReadLine().Split(' '), bTemp => Convert.ToInt32(bTemp))
        ;
        int total = getTotalX(a, b);

        tw.WriteLine(total);

        tw.Flush();
        tw.Close();
    }
}

同样，我看不到测试用例，所以我不知道究竟是什么问题。我逐行浏览了代码，找不到任何 OutOfBoundExceptions 或类似的东西，所以它必须是一个逻辑问题。谢谢您的帮助！

一个典型的样本涉及 3 行输入。第一行有 2 个整数，分别给出第一个数组和第二个数组的长度。第二行将给出第一个数组中的整数。第三行将给出第二个数组中的整数。输出需要是两个数组“之间”的整数总数。它看起来像这样：

样本输入

2 3
2 4
16 32 96

样本输出

3

解释：2 和 4 均分为 4、8、12 和 16。4、8
和 16 均分为 16、32、96。4、8
和 16 是仅有的三个数，第一个数组的每个元素都是factor 和 each 是第二个数组的所有元素的一个因子。

标签： c#arrays

解决方案

我发现您发布的代码有两个问题。

首先，正如@Hans Kesting所指出的，a = array[xx]在 for 循环中不会每次都更新。由于该变量a仅在一个地方使用，我建议只需将其替换array[xx]为并按如下方式完成：

    for(int xx = array.Length - 2; xx >= 0; xx--)
    {
        foreach(int b in commonMultiples.ToList())
        {
            if (b % array[xx] != 0)
            {
                commonMultiples.Remove(b);

为了您对循环的理解：每次编写循环时for都要正确递增，如下所示：afor

for(int xx = array.Length - 2, a = array[xx]; xx >= 0; xx--, a = array[xx])

循环的第一部分for（直到;）是初始化阶段，它只在第一次进入循环之前被调用。第二部分是在每次循环之前检查的 while 条件（包括第一个），如果在任何时候它评估为 false，则循环被破坏（停止）。第三部分是每次成功循环后才调用的增量阶段。

因此，为了a在循环头中保持最新for，它必须出现两次。

其次，您的solutionsingetTotalX是相加的，这意味着适用于数组中每个值的每个倍数都b作为解决方案添加，即使它不适合 .in 中的其他值b。为了让它以你想要的方式工作，我们必须使用Remove循环，而不是Add循环。

    List<int> multiples = getCommonMultiples(a, b_min);

    //create List to hold number of ints which are in solution
    List<int> solutions = multiples.ToList();
    foreach(int x in multiples)
    {
        foreach(int y in b)
        {
            if (y % x != 0)
            {
                solutions.Remove(x);
                break;
            }
        }
    }

您还可以使用 LINQ 执行加法解决方案，其中考虑以下All成员b：

    //create List to hold number of ints which are in solution
    List<int> solutions = multiples.Where((x) => b.All((y) => y % x == 0)).ToList();

推荐阅读