限定数组的转换步骤数

本文关键字：转换 数组 | 更新日期: 2023-09-27 18:04:15

嗨，谁能告诉我如何用c#解决这个问题?我有一个包含N个元素的数组。数组中的元素可以是正整数也可以是负整数。如果A=[11,3,7,1]我想计算使数组元素相等所需的最小变换步骤数。数组中的每个元素都可以加1或减1。

数组A需要5个变换步骤才能得到A =[6,6,6,6]

在每个转换中，每个元素必须递增或递减1。

[11, 3, 7, 1] (initial array)
[10, 4, 6, 2] (after step 1)
[9, 5, 7, 3] (after step 2)
[8, 6, 6, 4] (after step 3)
[7, 7, 5, 5] (after step 4)
[6, 6, 6, 6] (after step 5)

在某些数组中，这可能是不可能的。

例如

，对于[1,4,7]，不可能将元素等于一个数字。在这种情况下，它应该返回-1

限定数组的转换步骤数

假设你只是:

  • 查找最大元素
  • 查找最小元素
  • 所需的步数将是最大值和最小值之差的一半，四舍五入

你会找到最大和最小元素的平均值，向上或向下四舍五入-它不会影响步骤的数量-然后在每个转换步骤，你会调整每个数组元素的平均值。

编辑:很难看到你能比这更有效率。在每一步中，最大值和最小值元素彼此之间的距离不能超过2(最大值减少1，最小值增加1)，所以步骤数至少是差值的一半，四舍五入。我的解决方案还说明了如何以正好一半的差达到那个状态，四舍五入，所以这是一个具体的解决方案，没有更好的了。

编辑:下面是执行转换的代码。虽然效率不高，但它是有效的… 
using System;
using System.Linq;
class Test
{
    static void Main()
    {
        int[] current = new[] { 1, 3, 9, 11, 5 };
        // Check all odd or all even    
        if (current.Select(x => x % 2).Distinct().Skip(1).Any())
        {
            Console.WriteLine("No solution!");
            return;
        }
        while (current != null)
        {
            Console.WriteLine(string.Join(" ", current));
            current = Transform(current);
        }
    }
    static int[] Transform(int[] input)
    {
        // We could do the "mean" calculation just once,
        // but it doesn't really matter for the sake of
        // demonstration
        int max = input.Max();
        int min = input.Min();
        if (max == min)
        {
            // Done
            return null;
        }
        int mean = (max + min) / 2;
        return input.Select(x => x > mean ? x - 1 : x + 1)
                    .ToArray();
    }
}

这样行吗?

编辑对不起，这是

public int[] Equalize(int[] arr)
{
        int min = int.MaxValue;
        int max = int.MinValue;
        int parity = arr[0] % 2;
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] % 2 != parity) return null;
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }
        int diff = (max - min) / 2;            
        int midVal = diff + min;
        return arr.Select(i => midVal).ToArray();
}

ROUND_DOWN(SUM(each) / N)是否按预期工作?

Java 8版本Jon Skeet解决方案

public static void main(String[] args) throws FileNotFoundException {
         System.out.println(getTransformationCount(new int[] {1, 3, 9, 11, 5 }));
    }
    public static int getTransformationCount(int[] A) {
        int count = 0;
        A = Transform(A);
        if (IntStream.of(A).map(n -> n % 2).distinct().skip(1).count() > 0) {
            return -1;
        }
        while (A != null) {
            A = Transform(A);
            count++;
        }
        return count;
    }
    public static int[] Transform(int[] input) {
        int min = Arrays.stream(input).max().getAsInt();
        int max = Arrays.stream(input).min().getAsInt();
        if (max == min) {
            return null;
        }
        int mean = (max + min) / 2;
        return Arrays.stream(input).map((n) -> {
            if (n > mean)
                return n - 1;
            else
                return n + 1;
        }).toArray();
    }
相关文章：