现在有一组数据 1,3,5,7,8,9,10,20,21,22,23,24,25,40,41,42 混在一起现在要将这组数据分成 int[] Group1 = {1,3,5,7,9}
int[] Group2 = {20,21,22,23,24,25}
int[] Group3 = {40,41,42,43}以上示例的实际数据是胃排序的，也是随机生成的一组数据，但一定可以按某种连续性分成一组或N组，这样的算法如何写？
int[] Group2 = {20,21,22,23,24,25}
int[] Group3 = {40,41,42,43}以上示例的实际数据是胃排序的，也是随机生成的一组数据，但一定可以按某种连续性分成一组或N组，这样的算法如何写？
int temp = 10 //差值
int[] Group1 = {10 = temp*1 = 10*1}
int[] Group2 = {20 = temp*2 = 10*2}
int[] Group3 = {40 = temp*3 = 20*2}
int[] Group4 = {160 = temp*4 = 40*4}
......................
int[] GroupN = {temp = temp*N}
再举一个例子， 有一个大数组 PointF[]如果把这个数组用GDI+ 描点出来是三个椭圆（有可能相互包含）请问， 用什么算法将这个数组的点分离到对应的三个椭圆数组中
也许有bug,楼主自己改一下.其实这个题思想和最长递减子序列那种题很想,解法也差不多.
只不过还要考虑一下回溯,所以有stack.注释为伪码,因为我懒得再写quicksort和stack的源码.
不用stack会遗漏某些序列,但是你的示例输入不会有问题.
#include <stdio.h>
#include <stdlib.h>#define SIZE 16int main()
{
int arr[SIZE]={ 1,3,5,7,8,9,10,20,21,22,23,24,25,40,41,42 }; //arr=qsort(arr); int arrSub[SIZE-1]; for (int i=0;i<SIZE-1;i++)
{
arrSub[i]=arr[i+1]-arr[i];
} bool firstElement=true;
int subSofar=0;
int sub=arrSub[0]; //stackJ stackSub for (int j=1;j<SIZE-1;j++)
{
int curSub=arrSub[j];
if (curSub==sub)
{
if(firstElement)
{
printf("%d,%d,%d,",arr[j-1],arr[j],arr[j+1]);
firstElement=false;
}
else
{
printf("%d,",arr[j+1]);
}
}
else if(curSub<sub)
{
subSofar+=curSub;
if (subSofar==sub)
{
printf("%d,",arr[j+1]);
subSofar=0;
}
else if(subSofar>sub)
{
subSofar=0;
firstElement=true;
printf("\n");
}
}
else
{
if (curSub>=SIZE-1-j)
{
sub=arrSub[++j];
}
else
{
sub=curSub; //stackJ.push(j);
//stackSub.push(arrSub[j+1]);
}
firstElement=true;
subSofar=0;
printf("\n");
} // if(j==SIZE-1)
// {
// j=stackJ.pop();
// sub=stackSub.pop():
//}
}
system("pause");
return 0;
}
怎么分，是这样
int[] Group1 = {1,3,5,7}
int[] Group2 = {8,10,12}
还是这样
int[] Group1 = {1,3,5}
int[] Group2 = {7,8}
int[] Group3 = {10,12}1,3,5,20,35,36,37
怎么分，是这样
int[] Group1 = {1,3,5}
int[] Group2 = {20}
int[] Group3 = {35,36,37}
还是这样
int[] Group1 = {1,3,5}
int[] Group2 = {20,35}
int[] Group3 = {36,37}
或者是这样
int[] Group1 = {1,3}
int[] Group2 = {5,20,35}
int[] Group3 = {36,37}类似于上面的例子可以举出很多，那么哪种结果是对的？
如果你说分法一正确，分法二错误，那这是什么？这就是规则，既然是规则，为什么之前说没有
如果说就是没有规则，就是这样模糊的，那么我就可以认为哪种分法都是对的，或者说哪种分法都可以说是错的，这样此题就是无解
而按楼主楼主说法
就是规则模糊，要“智能”去找这个规律
这种题要么不是唯一解，要么就是无解
to lxcnn(过客) ：你举的例子第一个 1,3,5,7,8,10,12 分成的两组就是
int[] Group1 = {1,3,5,7,8}
int[] Group2 = {10,12}
第二个例子 1,3,5,20,35,36,37 分成的两组就是
int[] Group1 = {1,3,5,20}
int[] Group2 = {35,36,37}可能是我急于寻求答案，没有表述清楚，我说的是规则模糊，并不是没有任何规则，实际上规则是存在的，就我举的例子来阐述一下吧首先将数组排序 得到 1,3,5,7,8,9,10,20,21,22,23,24,25,40,41,42 循环计算前后两个数字的差值，并计算平均差 ，如 1,3,5,7,8,9,10 组的平均差为((3-1) + (5-3) +(7-5)+(8-7)+(9-8)+(10-9))/6
=1.5，接着一个数的差值(20-10) =10 ,大于 1.5, 所以可能编为另一组，注意只是可能，继续往后找，下一组是(21-20)=1, 比上一组差值小，这是可以确认
从10开始以后编为下一组。我们假设20后的数字是50，即1,3,5,7,8,9,10,20,50，51，54，58..., 那么20后的下一组差值就是(50-20) =30,比上一组(20-10)的差值还大，所以从20以后的数字可以编成一组。按照这种算法，直到找到所有的组。
再以你的第一个例子 1,3,5,7,8,10,12 为例
还是遍历， 到7为止， 平均差值为2， 到8为止，平均差值为1.75, 只要后面的两个数字差值大于1.75就可以可能分为另一组
这时，10－8 ＝2，大于 1.75, 而最后一组 12-10=2, 不大于前一组差值，所以从8以后的数组开始编为另一组。
using System;
using System.Collections.Generic;
using System.Text;namespace Test
{
class Program
{
static void Main(string[] args)
{
//测试数据
int[][] TestData = new int[][] {
new int[]{ 1, 3, 5, 7, 8, 9, 10, 20, 21, 22, 23, 24, 25, 40, 41, 42 },
new int[]{1, 3, 5, 7, 8, 10, 12} ,
new int[]{1, 3, 5, 20, 35, 36, 37},
new int[]{1, 3, 5, 7, 8, 9, 10, 20, 50 , 52, 51, 63, 75, 100, 150, 160, 1600}
};
//调用我方法
Console.WriteLine("My Result:");
CallMe(TestData);
//调用lxcnn的方法
Console.WriteLine("");
Console.WriteLine("");
Console.WriteLine("lxcnn's Result:");
Calllxcnn(TestData); Console.Read(); } #region 我的方法 private static void CallMe(int[][] TestData)
{
foreach (int[] textData in TestData)
PrintArray(BuildGroup(textData));
} private static void PrintArray(int[][] IntArray)
{
Console.WriteLine("-----------------------------------------------");
for (int i = 0; i < IntArray.Length; i++)
{
Console.Write(string.Format("int[] Group{0}", i + 1));
Console.Write(" = {");
for (int j = 0; j < IntArray[i].Length; j++)
{
Console.Write(IntArray[i][j]);
if (j < IntArray[i].Length - 1)
Console.Write(",");
}
Console.WriteLine("}");
}
} private static double Avg(int[] NumberList, int beginIndex, int endIndex)
{
double sum = 0;
for (int i = beginIndex; i < endIndex; i++)
sum += NumberList[i+1] - NumberList[i]; return sum==0 ? double.MaxValue : sum / (endIndex - beginIndex);
} private static int[][] BuildGroup(int[] NumberList)
{
ShellSort(ref NumberList);
List<int[]> list = new List<int[]>();
double diff; // 前后两数的差值
double diff_avg = double.NaN; //平均差
int i = 0;
int groupBegin = 0; //当前组的开始索引号
int count = NumberList.Length;
List<int> groupList = new List<int>();
while(i < count)
{
diff_avg = Avg(NumberList, groupBegin, i);
diff = i <count -1 ? NumberList[i+1] - NumberList[i] :0;
if (diff > diff_avg)
{
groupList.Add(NumberList[i]);
while (++i < count-1 && diff < (NumberList[i+1] - NumberList[i]))
{
groupList.Add(NumberList[i]);
} list.Add(groupList.ToArray()); //加入到当前组中
groupBegin = i; //重置当前组的开始索引号
groupList = new List<int>(); //重建下一组的数组列表 }
else
{
groupList.Add(NumberList[i]);
i++;
}
} //将剩余的数组加入到列表中的最后一个位置
if(groupList.Count >0)
list.Add(groupList.ToArray()); return list.ToArray();
}
public static void ShellSort(ref int[] NumberList)
{
int Count = NumberList.Length;
for (int k = Count / 2; k > 0; k /= 2)
{
for (int i = 0; i < k; i++)
{
for (int j = i; j < Count; j += k)
{
int thisNumber = NumberList[j];
int t = j;
while (t >= k && thisNumber < NumberList[t-k])
{
NumberList[t] = NumberList[t - k];
t -= k;
}
NumberList[t] = thisNumber; }
}
} }
#endregion
#region lxcnn的方法 private static void Calllxcnn(int[][] TestData)
{
foreach (int[] textData in TestData)
PrintArray2(ArrSplit(textData)); } private static List<List<int>> ArrSplit(int[] src)
{
List<List<int>> group = new List<List<int>>();
List<int> list = new List<int>();
list.Add(src[0]);
double currSub = 0;
double lastSub = double.MaxValue;
int sum = 0;
for (int i = 1; i < src.Length; i++)
{
sum += (src[i] - src[i - 1]);
currSub = (double)sum / i;
if (currSub <= lastSub)
{
list.Add(src[i]);
lastSub = currSub;
}
else
{
group.Add(list);
list = new List<int>();
list.Add(src[i]);
lastSub = double.MaxValue;
} if (i == src.Length - 1)
{
if (list.Count > 0)
group.Add(list);
}
}
return group;
} private static void PrintArray2(List<List<int>> result)
{
Console.WriteLine("-----------------------------------------------"); for (int i = 0; i < result.Count; i++)
{
Console.Write(string.Format("int[] Group{0}", i + 1));
Console.Write(" = {");
for (int j = 0; j < result[i].Count; j++)
{
Console.Write(result[i][j]);
if (j < result[i].Count - 1)
Console.Write(",");
}
Console.WriteLine("}");
}
}
#endregion
}
}
执行结果----------------------------------------------------------------
My Result:
-----------------------------------------------
int[] Group1 = {1,3,5,7,8,9,10}
int[] Group2 = {20,21,22,23,24,25}
int[] Group3 = {40,41,42}
-----------------------------------------------
int[] Group1 = {1,3,5,7,8}
int[] Group2 = {10,12}
-----------------------------------------------
int[] Group1 = {1,3,5}
int[] Group2 = {20,35,36,37}
-----------------------------------------------
int[] Group1 = {1,3,5,7,8,9,10,20}
int[] Group2 = {50,51,52,63,75,100}
int[] Group3 = {150,160}
int[] Group4 = {1600}
lxcnn's Result:
-----------------------------------------------
int[] Group1 = {1,3,5,7,8,9,10}
int[] Group2 = {20,21,22,23,24,25}
int[] Group3 = {40,41,42}
-----------------------------------------------
int[] Group1 = {1,3,5,7,8}
int[] Group2 = {10,12}
-----------------------------------------------
int[] Group1 = {1,3,5}
int[] Group2 = {20,35,36,37}
-----------------------------------------------
int[] Group1 = {1,3,5,7,8,9,10}
int[] Group2 = {20,50,51,52}
int[] Group3 = {63,75}
int[] Group4 = {100,150,160}
int[] Group5 = {1600}
-----------------------------------------------
int[] Group1 = {1,3,20,40}
int[] Group2 = {60,61,62,63}
int[] Group3 = {70,71,72}
int[] Group4 = {1100}
lxcnn's Result:
-----------------------------------------------
int[] Group1 = {1,3}
int[] Group2 = {20,40}
int[] Group3 = {60,61,62,63,70,71,72}
int[] Group4 = {1100}结果也不同， 是因为lxcnn的算法中，在创建新的一组的时候，sum值没有置0