检查在List<；列表<；int>>；高效

本文关键字：gt lt 高效 int 列表 List 检查 | 更新日期: 2023-09-27 18:00:21

我有一组List<List<int>>数据，字符串表示如下（给出想法！）：

 {{1,3},{-1,-3},{2,5},{-2,-5},{-3,4},{-5,4},{3,5,-4},{6,-8},{7,-8},{-6,-7,8},{7,9},{-7,-9},{3,8,-10},{-3,-8,-10},{-3,8,10},{3,-8,10},{4,9,-11},{-4,-9,-11},{-4,9,11},{4,-9,11},{10,11},{-1,6},{1,-6},{-2,7},{2,-7}}

我想检查，在所有现有的数字中，是否存在一个仅以正形式存在的数字或一组数字。我的意思是，如果在整个数据中有3和-3，我应该返回false，否则我必须将3作为仅以正3存在的数字添加到另一个列表中。（只有否定的数字也是如此）

以下是我尝试的方法：

首先，生成一组唯一的数字并删除负数：

private void GenerateCurrentExistingVariables()
{
    _uid = new List<int>();
    var all = _cnf.Data.SelectMany(list => list).ToList();
    _uid = all.Distinct().ToList(); //make list unique
    _uid.Sort(); //sort numbers
    _uid.Reverse(); //reverse so highest numbers would evalaute first!
    _uid = _uid.Where(i => i >= 0).ToList(); //remove negative numbers
}

然后我做这样的事情：

在一个方法中，我调用以下代码：

    for (var i = 0; i < _uid.Count; i++)
    {
        if (ExistOnlyInNegatedForm(_uid[i]))
        {
            onlyNegatedList.Add(_uid[i]);
        }
        //perhaps continue
        if (ExistOnlyInPositiveForm(_uid[i]))
        {
            onlyPositiveList.Add(_uid[i]);
        }
    }

依次调用以下方法：

private bool ExistOnlyInPositiveForm(int id)
{
    for (var i = 0; i < _cnf.Data.Count; i++)
    {
        for (var j = 0; j < _cnf.Data[i].Count; j++)
        {
            if (_cnf.Data[i][j] == id)
            {
                return false;
            }
        }
    }
    return true;
}
private bool ExistOnlyInNegatedForm(int id)
{
    var toCheck = -id;
    for (var i = 0; i < _cnf.Data.Count; i++)
    {
        for (var j = 0; j < _cnf.Data[i].Count; j++)
        {
            if (_cnf.Data[i][j] == -toCheck)
            {
                return false;
            }
        }
    }
    return true;
}

对于这个简单的任务来说，这太多的代码了，我觉得随着数据越来越大，这会越来越慢。。。请告诉我该如何改进。此外，我希望使用LINQ来完成这项工作，至少是为了减少代码行数！

我也想看到一个C++解决方案，所以我在我的问题中标记C++（不是做语言垃圾邮件！）

检查在List<；列表<；int>>；高效

对于正数：

var uids = _uid.SelectMany(q => q).ToArray();
var positive = uids.Where(p => p >= 0).Distinct()
    .Except(uids.Where(p => p < 0).Select(p => -p))
    .ToList();
return positive.Any();

对于负数：

var negative = uids.Where(p => p < 0).Distinct()
    .Except(uids.Where(p => p >= 0).Select(p => -p))
    .ToList();
return negative.Any();

我一直在考虑这个想法，到目前为止，这个想法似乎奏效了。当然，我不得不稍微修改你的数据集，因为事实上，没有一个数字通过了只有阳性或阴性的测试。

所以，这是：

  //Setting up the mock data
  List<List<int>> data = new List<List<int>>();
  data.Add(new List<int>(new[] { 1, 3 }));
  data.Add(new List<int>(new[] { -1, -3 }));
  data.Add(new List<int>(new[] { 2, 5 }));
  data.Add(new List<int>(new[] { -2, -5 }));
  data.Add(new List<int>(new[] { -3, 4 }));
  data.Add(new List<int>(new[] { -5, 4 }));
  data.Add(new List<int>(new[] { 3, 5, -4 }));
  data.Add(new List<int>(new[] { 6, -8 }));
  data.Add(new List<int>(new[] { 7, -8 }));
  data.Add(new List<int>(new[] { -6, -7, 8 }));
  data.Add(new List<int>(new[] { 7, 9 }));
  data.Add(new List<int>(new[] { -7, -9 }));
  data.Add(new List<int>(new[] { 3, 8, -10 }));
  data.Add(new List<int>(new[] { -3, -8, -10 }));
  data.Add(new List<int>(new[] { -3, 8, 10 }));
  data.Add(new List<int>(new[] { 3, -8, 10 }));
  data.Add(new List<int>(new[] { 4, 9, -11 }));
  data.Add(new List<int>(new[] { -4, -9, -11 }));
  data.Add(new List<int>(new[] { -4, 9, 11 }));
  data.Add(new List<int>(new[] { 4, -9, 11 }));
  data.Add(new List<int>(new[] { 10, 11 }));
  data.Add(new List<int>(new[] { -1, 6 }));
  data.Add(new List<int>(new[] { 1, -6 }));
  data.Add(new List<int>(new[] { -2, 7 }));
  data.Add(new List<int>(new[] { 2, 39 }));
  //Actual solution code
  var all = data.SelectMany(l => l); //flatten
  var grouped = all.GroupBy(g => Math.Abs(g)); //Group
  //Look for groups where the Sum is equal Key * Count, 
  //which means only either all positives, or all negatives
  var good = grouped.Where(i => i.Key * i.Count() == Math.Abs(i.Sum())); 
  var result = good.Select(g => g.First()); //Get rid of groups
  var allPos = result.Where(i => i > 0); //Self explanatory
  var allNeg = result.Where(i => i < 0);

我已经拆分了每个步骤，但可以很容易地将linq内容重写为一个长查询。

干杯

你为什么不写一个简单的方法，它会接受一个int列表，一个布尔值，表示你想要正和负，它只会返回true-false
通过这种方式，您可以遍历外部列表，为其中的每个元素调用它，如果您得到了所需的内容，则从那里继续：

public int AllSameSign(IEnumerable<int> theInputList, bool positive = true)
{
     if (positive)
         return theInputList.All(i=>i >= 0);
     else
         return theInputList.All(i=>i < 0);
}

（这是我的想法，你可以把bool改成一个简单的枚举，让它更可读…）

既然你提到你可能想要一个c++答案，我就写了一个。它使用哈希表来存储整数的绝对值的键值对，以及存储该特定绝对值历史的对象。

历史跟踪对象定义如下：

int sign(int a){return ((a > 0) - (a < 0));}
int absolute(int a){return a * sign(a);}
struct SignRecord{
    SignRecord() : value_{NEITHER}{}
    enum SignGrouping{
        NEITHER, NEGATIVE, POSITIVE, BOTH
    } value_;
    SignGrouping& modify(int modifier){
        auto intToGrouping = [](int a)->SignGrouping {return a < 0 ? NEGATIVE : POSITIVE;};
        if(value_ == NEITHER){value_ = intToGrouping(modifier);}
        else if(value_ == BOTH){return value_;}
        else if(value_ == intToGrouping(modifier)){return value_;}
        else{
            return value_ = BOTH;
        }
        return value_;
    }
};

由于哈希表需要默认构造对象，以便按键引用表中的元素，这就是我选择在哈希表中插入和修改元素的方式，因此有一个默认构造函数，其状态存储一个既没有找到正值也没有找到负值的指示符。但是，只有在没有调用"修改"值的情况下，这种状态才会持续。我立即调用modify成员函数，这样它就不会出现在最终输出中。

modify函数根据输入整数的符号将NEITHER值转换为NEGATIVE或POSITIVE值。只有当对modify的调用是一个符号相反的整数时，这两种状态才会分别变为BOTH状态

最好的部分是，您只需要在列表集中迭代一次，然后您就可以所有整数分组。

这可以通过c++14:中可用的语法范围巧妙地完成

std::unordered_map<int, SignRecord>
    intOrganizer;
for(auto &&subList : myInts){
    for(auto &&entry : subList){
        intOrganizer[absolute(entry)].modify(entry);
    }
}

coliru演示位于此处。请注意，我修改了您给定的输入列表，因为在列表列表中，每个输入整数似乎都用两个符号表示。

只需以这种方式创建自己的IEquality比较器：

 class OnlyPositiveInt : IEqualityComparer<int>
    {
        public bool Equals(List<int> some)
        {
            if ( some.First() > 0 && some.Last() > 0)   { return true; }
            return false;
        }
        public int GetHashCode(int x)
        {
            return x.GetHashCode();
        }
    }
 List<List<int>> onlyPositive = new List<List<int>>(generatedList.Distinct(OnlyPositiveInt));
相关文章：