哪位大哥给个效率高一点的算法
public class Block
{
public int small;
public int big;
} public class BlockOperater
{
public List<Block> CombineBlock(List<Block> block1 , List<Block> block2)
{
//把 block1 ,block2 合并 ,就是取交集 ,怎么算阿.
//对于block1 , block2 内部已经是按小到大排序了
//要达到的目的就是 比如
//block1 是 (1,4)(6,11)(15,20)
//block2 是 (2,5)(8,16)
//返回的结果就是 (2,4)(8,11),(15,16)
}
}
public class Block
{
public int small;
public int big;
} public class BlockOperater
{
public List<Block> CombineBlock(List<Block> block1 , List<Block> block2)
{
//把 block1 ,block2 合并 ,就是取交集 ,怎么算阿.
//对于block1 , block2 内部已经是按小到大排序了
//要达到的目的就是 比如
//block1 是 (1,4)(6,11)(15,20)
//block2 是 (2,5)(8,16)
//返回的结果就是 (2,4)(8,11),(15,16)
}
}
public static List<Block> CombineBlock(List<Block> block1, List<Block> block2)
{
//取得共同的数量值
int count = Math.Min(block1.Count, block2.Count);
List<Block> blocks = new List<Block>();
for (int i = 0; i < count; i++)
{
blocks.Add(new Block(block2[i].small, block1[i].big));
}
if (count > block1.Count)
{
//block1的数量多
int big = block2[count - 1].big;
for (int i = count; i < block1.Count; i++)
{
blocks.Add(new Block(block1[i].small,big));
}
}
else if(count > block2.Count)
{
//block2的数量多
int small = block1[count - 1].small;
for (int i = count; i < block2.Count; i++)
{
blocks.Add(new Block(small,block2[i].big));
}
} return blocks;
}
但是有点结果有点错误啊
List<Block> block1 = new List<Block>();
block1.Add(new Block(1,4));
block1.Add(new Block(7, 10));
block1.Add(new Block(15, 20)); List<Block> block2 = new List<Block>();
block2.Add(new Block(2, 5));
block2.Add(new Block(8, 9));
block2.Add(new Block(11, 18)); List<Block> newblocks = new List<Block>(); newblocks = CombineBlock(block1,block2);
返回的是 (2,4) ,(8,10),(11,20)实际上期望的 应该是 (2,4) ,(8,9),(15,18)
我先看一下你的算法
所以取中间的 是 8和9
{
public List<Block> CombineBlock(List<Block> block1, List<Block> block2)
{
List<Block> result = new List<Block>(block1.ToArray()); Stack<Block> stack = new Stack<Block>();
for (int i = block2.Count - 1; i >= 0; i--)
stack.Push(block2[i]); while (stack.Count != 0)
{
Block tempBlock = stack.Pop(); for (int i = 0; i < result.Count; i++)
{
if(tempBlock.small >= result[i].big)
{
if (i < result.Count - 1)
continue;
}
else if (tempBlock.big <= result[i].small)
{
}
else
{
if (tempBlock.big >= result[i].big)
{
stack.Push(new Block(result[i].big, tempBlock.big));
} result[i].small = Math.Max(tempBlock.small, result[i].small);
result[i].big = Math.Min(tempBlock.big, result[i].big);
} break;
}
} return result;
}
}
public class Block
{
public int small;
public int big;
} public class BlockOperater
{
/*
把 block1 ,block2 合并 ,就是取交集 ,怎么算阿.
对于block1 , block2 内部已经是按小到大排序了
要达到的目的就是 比如
block1 是 (1,4)(6,11)(15,20)
block2 是 (2,5)(8,16)
返回的结果就是 (2,4)(8,11),(15,16)
*/
public List <Block> CombineBlock(List <Block> block1 , List <Block> block2)
{
List<Block> list = new List<Block>();
foreach(Block b1 in block1)
{
foreach(Block b2 in block2)
{
if((b1.big <= b2.small) || (b1.small >= b2.big)) continue;
else if((b1.big < b2.big) && (b1.small < b2.small))
{
list.Add(b2.small,b1.big);
}
else if((b1.big < b2.big) && (b1.small > b2.small))
{
list.Add(b1.small,b1.big);
}
else if((b1.big > b2.big) && (b1.small < b2.small))
{
list.Add(b2.small,b2.big);
}
else if((b1.big > b2.big) && (b1.small > b2.small))
{
list.Add(b1.small,b2.big);
}
}
}
return list;
}
2.如果struct足够用就不需要class...
3.要会分解问题...
4.不要用OP的做法解决OO的问题...
public struct Block
{
public int Small;
public int Big; public Block(int small, int big)
{
Small = small;
Big = big;
} public static Block Intersect(Block block1, Block block2)
{
Block result = new Block();
result.Small = block1.Small >= block2.Small ? block1.Small : block2.Small;
result.Big = block1.Big <= block2.Big ? block1.Big : block2.Big;
return result;
} public static List<Block> Intersect(List<Block> blocks1, List<Block> blocks2)
{
List<Block> result = new List<Block>();
List<Block> m, n;
if (blocks1.Count >= blocks2.Count)
{
m = blocks1;
n = blocks2;
}
else
{
m = blocks2;
n = blocks1;
}
for (int i = 0; i < m.Count; i++)
{
if (n.Count > i)
{
result.Add(Block.Intersect(m[i], n[i]));
}
else
{
result.Add(m[i]);
}
}
return result;
}
}
不过从算法结果上来讲 除了 changjiangzhibin 的结果多有点问题
比如 数据源是
(1,4)),(7, 10),(15, 20)和(2, 5),(11, 21)
zhangenter 的结果是 (2,4)(7,10)(15,20)
vrhero 的是 (2,4)(11,10)(15,20)
实际上应该是(2,4)(15,20)的
{
#region " Variables " private Int32 _lowBound;
private Int32 _highBound;
public static readonly Block Empty = new Block(0, 0); #endregion #region " Properties " public Int32 LowBound
{
get { return _lowBound; }
private set { _lowBound = value; }
}
public Int32 HighBound
{
get { return _highBound; }
private set { _highBound = value; }
} #endregion #region " Constructor " public Block(Int32 lowBound, Int32 highBound)
{
if (lowBound > highBound) throw new ArgumentException("上限不能低于下线");
this.LowBound = lowBound;
this.HighBound = highBound;
} #endregion #region " Methods " public Block Intersects(Block block)
{
if (Object.ReferenceEquals(block, null)) return null;
int lowBound = (this.LowBound >= block.LowBound) ? this.LowBound : block.LowBound;
int highBound = (this.HighBound <= block.HighBound) ? this.HighBound : block.HighBound;
if (highBound <= lowBound) return Block.Empty;
return new Block(lowBound, highBound);
}
public Block MergeWithRemovingOverlaps(Block block)
{
Block intersectBlock = this.Intersects(block);
if (intersectBlock == Block.Empty) return Block.Empty; Int32 lowBound = (this.LowBound < block.LowBound) ? this.LowBound : block.LowBound;
Int32 highBound = (this.HighBound > block.HighBound) ? this.HighBound : block.HighBound;
return new Block(lowBound, highBound);
}
public Int32 CompareTo(Block other)
{
if (Object.ReferenceEquals(other, null)) return 1;
else if (this.LowBound < other.LowBound) return -1;
else if (this.LowBound > other.LowBound) return 1;
else if (this.HighBound < other.HighBound) return -1;
else if (this.HighBound > other.HighBound) return 1;
else return 0;
}
public Object Clone()
{
return new Block(this.LowBound, this.HighBound);
}
public override Boolean Equals(Object obj)
{
if (obj == null) return false;
if (this.GetType() != obj.GetType()) return false; Block objBlock = obj as Block;
if (this.LowBound != objBlock.LowBound) return false;
if (this.HighBound != objBlock.HighBound) return false; return true;
}
public override Int32 GetHashCode()
{
return this.LowBound * this.HighBound;
}
public override string ToString()
{
return string.Format("({0}, {1})", this.LowBound, this.HighBound);
}
public static Boolean operator ==(Block b1, Block b2)
{
return Object.Equals(b1, b2);
}
public static Boolean operator !=(Block b1, Block b2)
{
return !(b1 == b2);
}
public static Boolean operator >(Block b1, Block b2)
{
if (Object.ReferenceEquals(b1, null)) return false;
return b1.CompareTo(b2) == 1;
}
public static Boolean operator <(Block b1, Block b2)
{
if (Object.ReferenceEquals(b2, null)) return false;
return b2.CompareTo(b1) == 1;
}
public static Boolean IsNullOrEmpty(Block block)
{
return Object.ReferenceEquals(block, null) || block == Block.Empty;
} #endregion
}
{
public Int32 Compare(Block x, Block y)
{
if (Object.ReferenceEquals(x, null) && Object.ReferenceEquals(y, null)) return 0;
if (!Object.ReferenceEquals(x, null) && !Object.ReferenceEquals(y, null))
{
if (x == y) return 0;
if (x.LowBound < y.LowBound) return -1;
else if (x.LowBound > y.LowBound) return 1;
else if (x.HighBound < y.HighBound) return -1;
else if (x.HighBound > y.HighBound) return 1;
else return 0;
}
else if (Object.ReferenceEquals(x, null)) return -1;
else return 1;
}
}
{
#region " Constructor " public BlockList()
{
this.BlockSets = new List<Block>();
} #endregion #region " Methods " public Boolean Contains(Block block)
{
return this.BlockSets.Contains(block);
}
public IEnumerator<Block> GetEnumerator()
{
foreach (Block b in this.BlockSets)
{
yield return b;
}
}
public void Add(Block block)
{
if (this.BlockSets.Contains(block)) return;
// Find the block intersected
for (int i = 0; i < this.BlockSets.Count; i++)
{
Block b = this.BlockSets[i] as Block;
if (Object.ReferenceEquals(b, null)) continue;
if (!Block.IsNullOrEmpty(b.Intersects(block)))
{
b = b.MergeWithRemovingOverlaps(block);
return;
}
}
this.BlockSets.Add(block);
}
public void Clear()
{
this.BlockSets.Clear();
}
public void Sort(IComparer<Block> comparer)
{
this.BlockSets.Sort(comparer);
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.BlockSets.GetEnumerator();
} #endregion #region " Properties " private List<Block> BlockSets
{
get
{
return _blockSets;
}
set
{
if (!Object.ReferenceEquals(_blockSets, null)) _blockSets.Clear();
_blockSets = value;
}
}
public Block this[int index]
{
get
{
return this.BlockSets[index] as Block;
}
set
{
this.BlockSets[index] = value;
}
}
public Int32 Count
{
get
{
return this.BlockSets.Count;
}
} #endregion #region " Variables " private List<Block> _blockSets = null; #endregion }
public class BlockOperator
{
public static BlockList CombineBlocks(BlockList blockList1, BlockList blockList2)
{
BlockList combineBlockList = new BlockList();
for (int i = 0, j = 0; i < blockList1.Count && j < blockList2.Count; )
{
// 相交部分
Block newBlock = blockList1[i].Intersects(blockList2[j]);
// 判断是否相交为空
if (Block.IsNullOrEmpty(newBlock))
{
if (blockList1[i] < blockList2[j])
{
if (i == blockList1.Count - 1) break;
if (j != 0) --j;
i++;
}
else
{
if (j != blockList2.Count - 1) ++j;
else break;
}
}
else
{
combineBlockList.Add(newBlock);
if (j != blockList2.Count - 1) ++j;
else break;
}
}
return combineBlockList;
}
public static void Main()
{
BlockComparer bComparer = new BlockComparer(); BlockList blist1 = new BlockList();
blist1.Add(new Block(1, 4));
blist1.Add(new Block(7, 10));
blist1.Add(new Block(15, 20)); blist1.Sort(bComparer);
foreach (Block b in blist1)
{
Console.WriteLine(b.ToString());
}
Console.WriteLine("============================"); BlockList blist2 = new BlockList();
blist2.Add(new Block(2, 5));
blist2.Add(new Block(11, 21));
blist2.Sort(bComparer);
foreach (Block b in blist2)
{
Console.WriteLine(b.ToString());
}
Console.WriteLine("============================"); BlockList blist3 = BlockOperator.CombineBlocks(blist1, blist2);
foreach (Block b in blist3)
{
Console.WriteLine(b.ToString());
}
}
}