配列のピークを特定
7191 ワード
このテーマは2つのタイプに分かれています.
1.一次元配列のピークを探す
整数配列(sizeはn)を与え、以下の特徴を有します.の隣接する位置の数字は異なる である. A[0]A[n−1] Pがピークの位置であると仮定すると
1次元配列のピークを探して、最も暴力的な方法はfor循環で、1つの要素ごとに左右の両側の値を比較して、時間の複雑度O(N),.
また,実際に最適なアルゴリズムは二分法,O(log N)である.
2.二次元配列のピークを探す
整数行列には、次のような特性があります.隣接する整数はすべて異なる である.行列にはn行m列がある. すべてのiA[n-1][i]がある. すべてのjA[j][m-1]がある.
位置Pがピークであると定義し,A[j][i]>A[j+1][i]&&A[j][i]>A[j-1][i]&&A[j][i]>A[j][i]>A[j][i+1]&&A[j][i]>A[j][i]>A[j][i]がある場合を定義する.
この行列の1つのピーク要素を探し出して、彼の座標の解題の構想に戻って依然として2分で、行の2分で、同じく2分を列挙することができて、このような時間の複雑度O(N log N)、以下の解法5を参照します
最良の方法は行列同時二分O(N)である.
最後の解法は最適な解法であり,行と列は同時に二分され,同様に一次元配列を利用してピークを探す思想である.時間の複雑さはO(N)であるが,なぜかというと,以下に証明する.
2分プロセスでは、行に対して中間行の最大値を2分スキャンし、行ごとにN個の数をスキャンし、列に対して2分して中間列の最大値を探します.この場合、前に2分したため、各列はn/2(または同じ桁)の数しかありません.その後、(N/2)小さなマトリクスのピークを見つけます.これは同じサブ問題です.そこでT(N)=N+N/2+T(N/2)=3/2*N+O(N)T(N/2)=3/2*(N/2)+O(N/4)+T(N/4)=3/2*(N/4)+O(N/8)T(N/k)=3/2*(N/k)+O(1)をこのように推定し,すべての式を加算して,T(N)=3/2*2 N+O(1)=O(N)を相殺した.
1.一次元配列のピークを探す
整数配列(sizeはn)を与え、以下の特徴を有します.
A[P] > A[P-1],A[P] > A[P+1]を満たし,配列のいずれかのピークの位置を返す.1次元配列のピークを探して、最も暴力的な方法はfor循環で、1つの要素ごとに左右の両側の値を比較して、時間の複雑度O(N),.
また,実際に最適なアルゴリズムは二分法,O(log N)である.
class Solution {
public:
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
// 1. for
int findPeak1(vector A) {
// write your code here
for(int i = 1; i < A.size()-1; i++){
if(A[i] > A[i-1] && A[i] > A[i+1]){
return i;
}
}
return -1;
}
// 2.
int findPeak2(vector A) {
if(A.size() < 3){
return -1;
}
int start = 1;
int end = A.size()-1;
while(start <= end){
int middle = start + (end - start) / 2;
if(A[middle] < A[middle-1]){
end = middle-1;
}
else if(A[middle] < A[middle+1]){
start = middle+1;
}
else {
return middle;
}
}
return -1;//should never happen
}
// 3. ( )
int findPeak(vector A) {
if(A.size() < 3){
return -1;
}
int start = 1;
int end = A.size()-2;
while(start+1 < end){
int middle = start + (end - start) / 2;
if(A[middle] < A[middle-1]){
end = middle;
}
else if(A[middle] < A[middle+1]){
start = middle;
}
else {
start = middle;
}
}
if(A[start] > A[end]){
return start;
}
return end;
}
}; 2.二次元配列のピークを探す
整数行列には、次のような特性があります.
位置Pがピークであると定義し,A[j][i]>A[j+1][i]&&A[j][i]>A[j-1][i]&&A[j][i]>A[j][i]>A[j][i+1]&&A[j][i]>A[j][i]>A[j][i]がある場合を定義する.
この行列の1つのピーク要素を探し出して、彼の座標の解題の構想に戻って依然として2分で、行の2分で、同じく2分を列挙することができて、このような時間の複雑度O(N log N)、以下の解法5を参照します
最良の方法は行列同時二分O(N)である.
class Solution {
/**
* @param A: An integer matrix
* @return: The index of the peak
*/
// 4， O(N * M)
public List findPeakII3(int[][] A) {
// write your code here
List ans = new ArrayList();
int n = A.length;
int m = A[0].length;
for(int i = 1; i < n-1; i++){
for(int j = 1; j < m-1; j++){
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
if( A[i][j] > A[i+dx[0]][j+dy[0]] &&
A[i][j] > A[i+dx[1]][j+dy[1]] &&
A[i][j] > A[i+dx[2]][j+dy[2]] &&
A[i][j] > A[i+dx[3]][j+dy[3]]){
ans.add(i);
ans.add(j);
return ans;
}
}
}
return ans;
}
// 5， ， O(N log N)
public List findPeakII4(int[][] A) {
List ans = new ArrayList();
int n = A.length;
int m = A[0].length;
if(n < 3){
return ans; // argument check
}
int start = 1, end = n-2;
while(start <= end){
int row = start + (end - start) / 2;
int col = findLargest(A, row);
if(A[row][col] < A[row-1][col]){
end = row - 1;
}
else if(A[row][col] < A[row+1][col]){
start = row + 1;
}
else{
ans.add(row);
ans.add(col);
return ans;
}
}
return ans;
}
// find largest in a row, return col index
public int findLargest(int [][] A, int row){
int col = 0;
for(int j = 0; j < A[0].length; j++){
if(A[row][j] > A[row][col]){
col = j;
}
}
return col;
}
// ， ， O(N)
public List findPeakII(int[][] A) {
List ans = new ArrayList();
int n = A.length;
int m = A[0].length;
if(n < 3 || m < 3){
return ans; // argument check
}
int start_row = 1, end_row = n-2;
int start_col = 1, end_col = m-2;
int row = 0, col = 0; // store middle
while(start_row <= end_row && start_col <= end_col){
// search row
row = start_row + (end_row - start_row) / 2;
col = findLargestInRow(A, row, start_col, end_col);
if(A[row][col] < A[row-1][col]){
end_row = row - 1;
}
else if(A[row][col] < A[row+1][col]){
start_row = row + 1;
}
else{
ans.add(row);
ans.add(col);
return ans;
}
// search column
col = start_col + (end_col - start_col) / 2;
row = findLargestInCol(A, col, start_row, end_row);
if(A[row][col] < A[row][col-1]){
end_col = col - 1;
}
else if(A[row][col] < A[row][col+1]){
start_col = col + 1;
}
else{
ans.add(row);
ans.add(col);
return ans;
}
}
return ans;
}
// search larget one in a row, return col index
public int findLargestInRow(int [][] A, int row, int start_col, int end_col){
int col = start_col;
for(int j = start_col; j <= end_col; j++){
if(A[row][j] > A[row][col]){
col = j;
}
}
return col;
}
// search largest one in a col, return row index;
public int findLargestInCol(int [][] A, int col, int start_row, int end_row){
int row = start_row;
for(int i = start_row; i <= end_row; i++){
if(A[i][col] > A[row][col]){
row = i;
}
}
return row;
}
}
最後の解法は最適な解法であり,行と列は同時に二分され,同様に一次元配列を利用してピークを探す思想である.時間の複雑さはO(N)であるが,なぜかというと,以下に証明する.
2分プロセスでは、行に対して中間行の最大値を2分スキャンし、行ごとにN個の数をスキャンし、列に対して2分して中間列の最大値を探します.この場合、前に2分したため、各列はn/2(または同じ桁)の数しかありません.その後、(N/2)小さなマトリクスのピークを見つけます.これは同じサブ問題です.そこでT(N)=N+N/2+T(N/2)=3/2*N+O(N)T(N/2)=3/2*(N/2)+O(N/4)+T(N/4)=3/2*(N/4)+O(N/8)T(N/k)=3/2*(N/k)+O(1)をこのように推定し,すべての式を加算して,T(N)=3/2*2 N+O(1)=O(N)を相殺した.