算法性能比较（二）——找出特殊的奇偶数

悠悠 2022-05-31 09:19 193阅读 0赞

原题简单描述如下：  
给定一个数组，数组包含至少3个元素，所有元素均为整数，且所有元素符合：只包含一个偶数其余全部为奇数或只包含一个奇数其余全部为偶数，找出这个单独的偶数/奇数。

下面给出算法：

最佳算法：

function findOutlier(int){ 
      var even = int.filter(a=>a%2==0);
      var odd = int.filter(a=>a%2!==0);
      return even.length==1? even[0] : odd[0];
    }

算法理解：计算数组中的偶数个数和奇数个数，返回唯一的偶数/奇数。

我的算法：

算法理解（真的丑啊，哈哈）：记录第一个数的奇偶，然后记录下一个与第一个数奇偶性不同的数（如果这个数是数组的最后一个数，则这个数就是唯一的偶数/奇数），再根据再下一个数的奇偶性来判断之前记录的两个数哪一个是唯一的偶数/奇数。

接下来是性能比较，比较代码：

构造一个长度为10000001且只包含一个偶数其余全部为奇数的数组，唯一的偶数在数组最后：

<table> 
 <thead> 
  <tr> 
   <th>验证次数</th> 
   <th>最佳算法用时</th> 
   <th>我的算法用时</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>第一次</td> 
   <td>439</td> 
   <td>1998</td> 
  </tr> 
  <tr> 
   <td>第二次</td> 
   <td>454</td> 
   <td>2092</td> 
  </tr> 
  <tr> 
   <td>第三次</td> 
   <td>448</td> 
   <td>2043</td> 
  </tr> 
 </tbody> 
</table>

![第一次][20180217232147534]  
![第二次][20180217232240257]  
![第三次][20180217232337643]

最佳算法性能稳定在我的5倍左右，接下来调整一下比较代码：

构造一个长度为10000001且只包含一个偶数其余全部为奇数的数组，唯一的偶数在数组最前：

<table> 
 <thead> 
  <tr> 
   <th>验证次数</th> 
   <th>最佳算法用时</th> 
   <th>我的算法用时</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>第一次</td> 
   <td>453</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>第二次</td> 
   <td>460</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>第三次</td> 
   <td>528</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

![第一次][20180217232719436]  
![第二次][20180217232754591]  
![第三次][20180217232831538]

我的算法在这种情况下用时接近为0。

总结：我的算法性能与特殊数在数组中的位置有关，特殊数越靠前，则我的算法性能优于最佳算法，特殊数越靠后，则最佳算法性能优于我的算法，不过从代码简洁程度和稳定性两个角度来考虑，最佳算法完爆我的算法（除非我的算法在最差情况下——即特殊数是最后一个值时，性能与最佳算法仍然相近）。

[20180217232147534]: /images/20220531/c57e14ca837149d38a59669da41b8f7f.png
[20180217232240257]: /images/20220531/28b5a79c62d043cb80dcd7fedcdee610.png
[20180217232337643]: /images/20220531/02912b35bab7435bb0dc3c2fac81f1da.png
[20180217232719436]: /images/20220531/1681cead78b341198e46a8a98a957bb0.png
[20180217232754591]: /images/20220531/9cfc835377ff42f4a58073bf2c360d9a.png
[20180217232831538]: /images/20220531/7c68afb80977434199dc4fc57265339c.png