最长可整合子数组

可整合子数组：按由小到大排完序之后，后面的数比前一个数大1，如：[2,4,3,6,5]就是可整合数组。

 1 // getLiL.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 #include <hash_set>
 7 #include <iterator>
 8 #include <set>
 9 
10 using namespace std;
11 
12 void getLil(int *arr,int len)
13 {
14     if(arr == NULL || len <= 0)
15         return;
16 
17     int minNum = 0;
18     int maxNum = 0;
19     /*hash_set<int> mySet;*/  //hash_set行不通
20     set<int> mySet;
21     int result = 0;
22 
23     
24     for(int i = 0;i < len;i++)
25     {
26         minNum = 0x7fffffff;
27         maxNum = 0x80000000;
28         for(int j = i;i < len;j++)
29         {
30             set<int>::iterator ite;
31             if((ite=mySet.find(arr[j]))!=mySet.end())
32                 break;
33            //1.如果数组中有重复，一定不是可整合，直接进行下一次。
34             //利用set来判断时间复杂度为O(logn)
35             mySet.insert(arr[j]);
36 
37             //每一步都计算当前最大最小值，每一步都判断
38                          minNum = min(minNum,arr[j]);
39             maxNum = max(maxNum,arr[j]);
40             
41             if(maxNum - minNum == j - i)
42                 result = max(j - i + 1,result);
43             //2.一段范围中，最值之差等于下标之差，是可整合的
44         }
45         mySet.clear();
46     }
47     cout<<result<<endl;//result == 8
48 }
49 
50 int _tmain(int argc, _TCHAR* argv[])
51 {
52     int arr[] = {3,4,2,5,6,8,17,10,11,12,14,13,15,16};
53     getLil(arr,14);
54     system("pause");
55     return 0;
56 }

View Code

时间复杂度为O(n*n),这种方法用在不能改变数组元素的前提下，有最好的时间复杂度。

若是可以改变数组结构，直接可以利用排序，时间复杂度O(n*logn);