[leetcode] 300. Longest Increasing Subsequence解題レポート
3045 ワード
タイトルリンク:https://leetcode.com/problems/longest-increasing-subsequence/
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
考え方:O(n 2)の方法は,1つの配列hash[]を用いて,各位置の最も長いシーケンスがどれだけ長いかを記録することを容易に考えられる.各位置iを左に巡回し、位置jで彼より小さい数が見つかるまで、状態遷移方程式は、hash[i]=hash[j]+1である.
コードは次のとおりです.
もう一つの複雑度O(n*log(n))のやり方は容易には考えられない.
現在最も長いインクリメントシーケンスを維持するために、補助配列table[]も追加します.最も長いインクリメントシーケンスを維持するには、各位置の値をできるだけ小さくする必要があります.
配列の各値nums[i]には、次の2つの可能性があります.
1.nums[i]>table[len-1]の場合、シーケンスへの追加は依然として増加するので、nums[i]をシーケンスに追加し、シーケンス長を1とする
2.nums[i][10,9,2,5,3,7,101,18]を例に、増分シーケンスの成長を見てみましょう.
1)10
2)9
3)2
4)2, 5
5)2, 3
6)2, 3, 7
7)2, 3, 7,101
8)2, 3, 7, 18
本当に巧みな方法ですね.
コードは次のとおりです.
参照先:http://www.wutianqi.com/?p=1850
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given
[10, 9, 2, 5, 3, 7, 101, 18] , The longest increasing subsequence is [2, 3, 7, 101] , therefore the length is 4 . Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
考え方:O(n 2)の方法は,1つの配列hash[]を用いて,各位置の最も長いシーケンスがどれだけ長いかを記録することを容易に考えられる.各位置iを左に巡回し、位置jで彼より小さい数が見つかるまで、状態遷移方程式は、hash[i]=hash[j]+1である.
コードは次のとおりです.
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int maxLen = 0;
vector<int> hash(nums.size()+1, 1);
for(int i = 0; i< nums.size(); i++)
{
int j = i -1;
while(j >= 0)// nums[i]
{
if(nums[i] > nums[j])
hash[i] = max(hash[j]+1, hash[i]);
j--;
}
maxLen = hash[i]>maxLen?hash[i]:maxLen;//
}
for(int i = 0; i< nums.size(); i++)
cout << hash[i] << " ";
return maxLen;
}
};もう一つの複雑度O(n*log(n))のやり方は容易には考えられない.
現在最も長いインクリメントシーケンスを維持するために、補助配列table[]も追加します.最も長いインクリメントシーケンスを維持するには、各位置の値をできるだけ小さくする必要があります.
配列の各値nums[i]には、次の2つの可能性があります.
1.nums[i]>table[len-1]の場合、シーケンスへの追加は依然として増加するので、nums[i]をシーケンスに追加し、シーケンス長を1とする
2.nums[i]
1)10
2)9
3)2
4)2, 5
5)2, 3
6)2, 3, 7
7)2, 3, 7,101
8)2, 3, 7, 18
本当に巧みな方法ですね.
コードは次のとおりです.
class Solution {
public:
int findPos(const vector<int>& table, int value, int len)
{
int low =0, high = len-1;
while(low <= high)//
{
int mid = (low + high)/2;
if(value <= table[mid])
high = mid -1;
else
low = mid + 1;
}
return low;
}
int lengthOfLIS(vector<int>& nums) {
if(nums.size() == 0)
return 0;
vector<int> table(nums.size());//
int len = 1;
table[0] = nums[0];
for(int i = 1; i< nums.size(); i++)
{
if(nums[i] > table[len-1])
table[len++] = nums[i];
else
{
int pos = findPos(table, nums[i], len);
table[pos] = nums[i];
}
}
return len;
}
};参照先:http://www.wutianqi.com/?p=1850