1

我需要确定数字列表是否按真实顺序排列。特别是5的序列。

示例 1：

  • （原创系列） 1,3,4,67,43,20
  • （订购系列） 1,3,4,20,43,67
  • 是5的序列吗？ FALSE

示例 2

  • （原创系列） 147,10,143,432,144,23,145,146
  • （订购系列） 10,23,143,144,145,146,147,432
  • 是5的序列吗？ TRUE （即 143-147）

目前 - 我遍历有序列表，并检查当前数字是否等于最后一个数字 +1，并保留一个计数器。这行得通，但我很好奇是否有更好的方法来数学或编程。

<cfscript>
_list1 = [1,3,4,67,43,20]; // should evaluate to FALSE
_list2 = [147,10,143,432,144,23,145,146]; // should evaluate to TRUE

_list = _list2; // switch list in one place - test purposes only.
_seq = 1; // sequence counter
_cap = ''; // value of the upper most number of the sequence
_msg = 'There is not a consecutive sequence of 5.'; // message to user

// sort the array smallest to largest 
arraySort( _list, 'numeric' ); 

// loop the array - compare the last number with the current number 
for ( i=2; i LTE arrayLen( _list ); i++ ) {
    _last = _list[i-1]; // the LAST number - we started at the second element, so we shouldn't error.
    _this = _list[i]; // this current number
    // compare the two numbers
    if ( val( _this ) EQ val( _last ) + 1 ) {
        _seq = _seq + 1; // increment our sequence
        _cap = _this; // set the top number
    }
}

// re-set the message if we meet some threshold (5) is hardcoded here 
if ( val( _seq ) GTE 5 ) {
    _msg = 'Sequence of ' & _seq & ' to ' & _cap;
}

// write the message 
writeoutput( _msg );    
</cfscript>
4

4 回答 4

2

为了提高性能，我会说将您的循环包装在一个 IF 语句中，该语句首先检查至少有 5 个元素；没有必要循环超过 4 个元素。

然后我会说，如果'seq' = 5，请在循环内进行检查，并立即跳出循环（除非您实际上需要找出大于5的序列长度）。

您可能会考虑尝试的另一件事。在循环之前，您可以比较列表的第一个元素和列表的最后一个元素。如果它们之间的差异小于 5，则根本没有必要进行循环。尽管从您的数据看来，这可能不太可能发生。

于 2012-10-11T08:20:59.223 回答
1

听起来您想了解更多关于算法时间复杂度的信息（https://en.wikipedia.org/wiki/Time_complexity）。

您当前的算法首先进行排序，然后迭代所有元素。要确定你的算法的时间复杂度，我们首先要知道 Coldfusion 的排序算法的时间复杂度是多少。由于 Coldfusion 委托给 Java，并且Java 数组使用 QuickSort 算法，我们知道算法的排序部分需要n*log(n)时间。算法的第二部分迭代数组需要n时间。将这两个时间复杂度加在一起，我们得到n+(n*log(n)).

在分析算法的时间复杂度时，我们只关心最慢的部分：n*log(n). 因此，大 O 时间复杂度为O(n*log(n)).

这是什么意思？解决方案的排序部分是最糟糕的部分。如果您可以在不排序的情况下解决问题，那么您将提高应用程序的速度——假设您的新解决方案不会做任何比排序花费更多时间的事情。

于 2012-10-11T17:48:28.537 回答
0

我会从序列中创建一个数组，然后比较这个数组。这是一个很好的例子：链接

于 2012-10-10T19:41:49.863 回答
0

我把这个答案放在这里是因为我需要一个函数来输出一系列数字，其中任何超过 2 的内部序列按顺序作为连字符（即1,3,4,5,7as 1,3-5,7）并且在其他任何地方都没有快速找到它。您的代码看起来不比我的长，所以我的代码可能对您没有帮助，尽管它可以回答您的问题，因为 activecfreturn给出了最长的序列（您可以将其与您的 5 楼进行比较。（我的注释cfreturn给出了我需要的缩写内部序列）：

<cffunction name="fNumSeries" output="1" hint="pass in sorted array, get count of longest sequence">
<cfargument name="raNums" required="1" type="array">
<cfset numHold=raNums[1]>
<cfset isSeq="">
<cfset hasSeq=0>
<cfsavecontent variable="numSeries">
<cfloop from="1" to="#arraylen(raNums)#" index="idxItem">
    <cfif idxItem eq 1>#raNums[1]#<!--- always output the first --->
    <cfelse>
        <!--- if in a sequence and not the last array element, no output --->
        <cfif numHold+1 eq raNums[idxItem] and idxItem neq arraylen(raNums)>
            <!--- capture the first value of the sequence --->
            <cfif len(isSeq) eq 0><cfset isSeq=numHold></cfif>
        <cfelseif len(isSeq)><!--- was in sequence but no longer --->
            <!--- if more than 2 in a row, show as sequence (n-n) --->
            <cfif idxItem eq arraylen(raNums) and raNums[idxItem] gt isSeq+1>
                - #raNums[idxItem]#
                <cfif hasSeq lt numHold - isSeq+1><cfset hasSeq=numHold - isSeq+1></cfif>
            <cfelseif raNums[idxItem] gt isSeq+3>
                - #numHold#, #raNums[idxItem]#
                <cfif hasSeq lt numHold - isSeq+1><cfset hasSeq=numHold - isSeq+1></cfif>
            <!--- otherwise show the 2nd (held) sequential value and current array value --->
            <cfelse>, #isSeq+1#, #raNums[idxItem]#
            </cfif>
            <cfset isSeq="">
        <cfelse>, #raNums[idxItem]#<!--- not in sequence --->
        </cfif>
    </cfif>
    <cfset numHold=raNums[idxItem]>
</cfloop>
</cfsavecontent>
<!--- <cfreturn replace(numSeries, " ,", ",", "all")> --->
<cfreturn hasSeq>
</cffunction>
于 2014-12-03T19:14:03.477 回答