PHP 配列に対する一般的な操作の概要

配列の合計
n 個の要素を含む整数配列 a が与えられた場合、a 内のすべての要素の合計を求めます。とても単純だと思うかもしれません。確かに単純ですが、なぜそう言う必要があるのでしょうか。まず、この質問では 1 行のコードを使用するだけで再帰を使用する必要があります。第二に、これは私が人生で面接中に遭遇した最初の質問であり、特別な意味があります。

簡単に言うと、次の 2 つの状況があります:

配列の要素数が 0 の場合、合計は 0 になります。
配列の要素数が n の場合、最初に最初の n - 1 個の要素の合計を求め、次に a[n - 1] を加算します。
コードをコピー コードは次のとおりです:
//配列 sum
int sum(int *a, int n)
{
return n == 0 0 ? : sum(a, n - 1) + a[n - 1 ];
}

配列の最大値と最小値を求める
n 個の要素を含む整数配列 a を与えて、最大値と最小値を求めます。

従来のアプローチは、一度走査してそれぞれ最大値と最小値を見つけることですが、ここで説明するのは分割統治法 (Divide and Coquer) で、配列を左右の部分に分割し、まず左半分の最大値と最小値を求め、次に右半分の最大値と最小値を求め、それらを組み合わせて全体の最大値と最小値を求めます。これは再帰的なプロセスであり、分割後の左側と右側の部分について、分割された区間に要素が 1 つまたは 2 つだけ残るまでこのプロセスが繰り返されます。
コードをコピー コードは次のとおりです:
// 配列の最大値と最小値を検索します。戻り値は maxValue と minValue です
void MaxandMin(int *a, int l, int r, int& maxValue, int& minValue )
{
if(l == r) // l と r の間に要素は 1 つだけあります
{
maxValue = a[l] ;
minValue = a[l]
}

if(l + 1 == r) // l と r の間には要素が 2 つだけあります
{
if(a[l] >= a[r])
{
maxValue = a[l] ;
minValue = a[r] ] ;
}
else
{
maxValue = a[r] ;
minValue = a[l] ;
}

int m = (l + r) // 中間点を求める
int lmax ; // 左半分の部分最大値
int lmin // 左半分の最小値
MaxandMin(a, l, m, lmax, lmin) // 左半分の再帰計算

int rmax; // 右半分の最大値 Value
int rmin; // 右半分の最小値
MaxandMin(a, m + 1, r, rmax, rmin) // 右半分を再帰的に計算します

maxValue = max; (lmax, rmax); // 合計の最大値
minValue = min(lmin, rmin); // 合計の最小値
}


を含む整数配列を指定します。 n 個の要素から、その最大値と 2 番目に大きい値を見つけます。

このアイデアは前の質問と似ていますが、これも分割統治法を使用しています。詳細は省略します。コードを見てください:

コードをコピーします。コードは次のとおりです:
// 最大値と配列の 2 番目に大きい値であり、戻り値は
void MaxandMin(int *a, int left, int right, int &max, int &second) の max と 2 番目の間です
{
if(left == right)
{
最大 = a[左] ;
秒 = a[左]
}
else if(左 + 1 == 右)
{
最大 = a[左] : a [右] ;
秒 = a[左] < a[左] : a[右]
}
int = 左 + (右 - 左) / 2 int leftmax ;
MaxandMin(a, left, mid , leftmax, leftmin) ;
int rightmin(a, rightmax, rightmin) ; leftmax > leftmax : rightmax ;
next = leftmax < leftmax : rightmax ;


n 個の整数要素の配列を指定します。 、n / 2 より多く出現する要素が 1 つある場合、この要素を見つけます。百度の面接の質問だそうです。

現在の値と現在の値のカウンターを設定し、現在の値を配列の最初の要素に初期化します。カウンター値は 1 です。次に、走査された値 a[ ごとに 2 番目の要素から開始して配列全体を走査します。私]。

a[i]==currentValue の場合、カウンター値は 1 増加します。
a[i] != currentValue の場合、カウンター値は 1 減分されます。カウンター値が 0 未満の場合、現在の値は a[i] に更新され、カウンター値は 1 にリセットされます。
コードをコピーする コードは次のとおりです。
//配列内で半分以上出現する要素を検索します
int Find(int* a, int n)
{
int curValue = a[0]; int count = 1;

for (int i = 1; i

もう 1 つの方法は、要素の数が半分を超える場合、その要素が中央を占める必要があるため、最初に配列をソートしてから中央の要素を取得することです。配列がソートされた後の配列の位置

配列内の要素間の最短距離を見つけます
n 個の要素を含む整数配列が与えられた場合、abs(x - y) の値を最小にする配列内の 2 つの要素 x と y を見つけます。

まず配列を並べ替えてから、一度走査します:

コードをコピーする コードは次のとおりです:
int Compare(const void* a, const void* b)
{
return *(int*)a - *( int*) b ;

void MinimumDistance(int* a, int n)
// 並べ替え
qsort(a, n, sizeof(int), Compare) ; // 数値のインデックス1
int j ; // 数値 2 のインデックス

int minDistance = numeric_limits::max() ;
for (int k = 0; k {
if ( a[k + 1] - a[k] {
minDistance = a[k + 1] - a[k] ;
}
}

cout <}


2 つの順序付けされた配列の共通要素を見つけます
n 個の要素を含む 2 つの順序付けされた (降順ではない) 整数配列 a と b が与えられた場合、共通の要素を見つけますa = 0、1、2、3、4 および b = 1、3、5、7、9 として、1、3 を出力します。

配列の順序付けされた性質を最大限に活用し、2 つのポインター i と j を使用してそれぞれ a と b を指し、a[i] と b[j] を比較し、比較結果に従ってポインターを移動します。 3 つの状況:

a [i] < b[j]、その後、i が 1 増加し、比較を継続
a[i] == b[j]、その後、i と j の両方が 1 増加し、比較を継続
a[i]
i または j が配列の末尾に達するまで上記のプロセスを繰り返します。

コードをコピーします。 コードは次のとおりです。
//2 つの配列の共通要素を検索します
void FindCommon(int* a, int* b, int n)
{
int i = 0;
int j = 0; ;

while (i {
if (a[i] ++i ;
else if(a[i] == b[j] )
cout <<<}
else// a[j] ;
}
}


たとえば、a の任意の要素に対して b で二分検索を実行します。これは、a には n 個の要素があり、b で二分検索を実行するには logn が必要であるためです。 。したがって、すべての同じ要素を見つける時間計算量は O(nlogn) です。

さらに、上記の方法では、b の二分探索を実行しているだけなので、b が順序通りである限り、a が順序通りであるかどうかは関係ありません。 a も順序付けされている場合、上記の方法を使用すると少し遅くなります。 b の a の要素の位置が k の場合、 b の a の次の要素の位置は k の右側になければならないためです。したがって、今回の検索スペースは、全体をまだ検索するのではなく、最後の検索結果に基づいて絞り込むことができます。 b.つまり、a と b の両方が順序付けされている場合、コードを次のように変更して、最後の検索中の b 内の要素の位置を次の検索の開始点として記録できます。

3 つの配列の共通要素を見つける
n 個の要素を含む 3 つの整数配列 a、b、c が与えられた場合、それらの最小の共通要素を見つけます。

3 つの配列がすべて順序付けされている場合は、3 つの配列の先頭を指すように 3 つのポインターを設定し、共通の要素が見つかるまで 3 つのポインターが指す値の比較に基づいてポインターを移動できます。 。

コードをコピーする コードは次のとおりです:
// 3 つの配列の共通要素 - 最小のもののみを検索します
void FindCommonElements(int a[], int b[], int c[], int x, int y, int z )
{
for(int i = 0, j = 0, k = 0; i < x && j < y && k < z;)
{
if(a[i] < b[j] )
{
i++ ;
}
else // a[i] >= b[j]
{
if(b[j] {
j++ ;
else // b[ j] >= c[k]
{
if(c[k] < a[i])
{
k++ ;
}
else // c[k] >= a[i]
{
cout <}
}

"見つかりません!"
if 3 つの配列はすべて順序付けされていません。まず a と b を並べ替えてから、c の任意の要素に対して b と c で二分検索を実行できます。
コードをコピーする コードは次のとおりです:
// 3 つの配列で一意の共通要素を見つけます
// O(NlogN)
int UniqueCommonItem(int *a, int *b, int *c, int n)
{
/ / 配列 a をソート
qsort(a, n, sizeof(int), Compare) ; // NlogN

// 配列 b をソート
qsort(b, n, sizeof(int), Compare) ; // NlogN

/ / 配列 c の各要素に対して、a と b で二分探索を実行します
// これは最大 N*2*logN の複雑さになります
for (int i = 0; i < n; i++)
{
if(BinarySearch(a, n, c[i]) && BinarySearch(b, n, c[i]))
return c[i] ;
}

return - 1 ; // 見つかりません
}

a をソートしてから、b と c の任意の要素を実行することもできます。二分探索。
コードをコピーする コードは次のとおりです:
// 3 つの配列で一意の共通要素を見つけます
// O(NlogN)
int UniqueCommonItem1(int *a, int *b, int *c, int n)
{
/ / 配列 a をソート
qsort(a, n, sizeof(int), Compare) ; // NlogN

// 時間のためのスペース
bool *bb = new bool[n] ;

bool *bc = new bool[n] ;
memset(bb, 0, n) ;

// b の各要素に対して、a ですべての共通要素をマークします
for (int i = 0) ; i < ; n; i++) // NlogN
if(BinarySearch(a, n, b[i]))
bb[i] = true ;

// c の各要素に対して、 b[i] が true の場合のみ BS
for (int i = 0; i {
if(b[i] && BinarySearch(a, n, c[i]))
return c[ i] ;

return - 1 ; // 見つからない
}

ソートと二分探索のコードは次のとおりです:
// a に値 k が含まれているかどうかを判断します。
bool BinarySearch(int *a, int n, int k)
{
int left = 0 ;
int right = n - 1 ;
while (left <= right)
{
int mid = (left + right) ;

if(a[mid] < k)
left = Mid + 1 ;
if(a[mid] == k)
return true ;
right =mid - 1 ; ;
}

// qsort の比較関数
int Compare(const void* a, const void* b)
{
return *(int*)a - *(int*)b
}

;配列内での検索の問題は、次の 2 つの状況で処理できます:

指定された配列が正しい場合は、まず二分探索を考える必要があります。これには O(logn) が必要です。
指定された配列が順序付けされていない場合は、まず配列のソートを考える必要があります。多くのソート アルゴリズムは O(nlogn) 時間で配列をソートし、その後で二分探索を使用します。合計時間は依然として O( nlogn) です。
上記2点ができれば、ほとんどの配列探索問題は簡単に解けます。

配列内で重複する唯一の要素を見つけます
1 から 1000 までの整数を格納する 1001 個の要素を含む配列がある場合、1 つの整数だけが繰り返されます。この番号を見つけてください。

配列全体の合計を求め、1-1000の合計を引きます コードは省略しています。

奇数回出現する要素を見つける
n 個の要素を含む整数配列 a で、1 つの要素だけが奇数回出現する場合、この要素を見つけます。

任意の数値 k について、k ^ k = 0、k ^ 0 = k であるため、a のすべての要素が XOR 演算され、XOR の後に偶数の要素は 0 になり、奇数の要素だけが残ります。置いた。

int FindElementWithOddCount(int *a, int n)
{
int r = a[0] ;

for (int i = 1; i
指定された合計を満たす数値ペアを配列内で検索します
与えられた 2 つの数値順序整数配列 a と b には、それぞれ n 個の要素があります。指定された合計を満たす、つまり、a の要素 i と b の要素 j について、i + j = d を満たす数値のペアを見つけます (d は既知です)。 ) .

2 つのポインター i と j はそれぞれ配列の先頭と末尾を指し、2 つのポインターが交差するまで同時に両端から中央まで移動します。 コードは次のとおりです。指定された合計を満たす数値ペア
void.FixedSum(int* a, int* b, int n, int d)
{
for (int i = 0, j = n - 1; i < n && j > ;= 0)
{
if (a[ i] + b[j] < d)
++i ;
else if (a[i] + b[j] == d)
{
cout < < a[i] < < < b[j] <<
++i ; // a[i] j] > d
--j ;
}
}

サブセグメントの最大合計
整数配列 a が与えられた場合、合計が負の数である場合、それは次のようになります。 1、2、-5、6、8 のように 0 として計算され、6 + 8 = 14 が出力されます。

プログラミングに関する古典的な質問ですが、あまり言うことはありません。
コードをコピーする コードは次のとおりです。
//部分配列の最大合計
int Sum(int* a, int n)
{
int curSum = 0;
int maxSum = 0;
for (int i = 0; i { if (curSum + a[i] < 0)
curSum = 0;
else
{
curSum += a[i] ;
maxSum = max(maxSum, curSum);return maxSum;
}

最大サブセグメント積
整数値 a が与えられた場合、1、2、-8、12、7 などの最大の連続サブセグメントの積を求めると、出力は 12 * 7 になります。 = 84。

最大サブセグメント合計と同様に、負の数の場合に注意してください。
コードをコピーします。 コードは次のとおりです。
//部分配列の最大積
int MaxProduct(int *a, int n)
{
int maxProduct = 1; // 現在の位置での最大の正の積
int minProduct = 1; // 現在の位置での最小の負の積
int r = 1; // 結果、合計の最大乗算

for (int i = 0; i {
if (a[i] > 0)
{
maxProduct *= a[i];
minProduct = min(minProduct * a[i], 1)
}
else if (a[i] == 0)
{
maxProduct = 1; minProduct = 1; }
else // a[i] < 0
int temp = maxProduct;
maxProduct = max(minProduct * a[i], 1);
}

r = max(r, maxProduct);
}

return r;
}

配列循環シフト
n 個の要素を含む配列を右に k ビットずつ循環移動する場合、必要な時間計算量は O(n )、追加変数は 2 つだけ使用できます。これは、Microsoft の The Beauty of Programming で見られる質問です。

たとえば、配列 1 2 3 4 を右に 1 ビット循環シフトすると、4 1 2 3 になります。シフトの前後で 1 2 3 の順序は変わっていないことがわかりますが、 4 の位置を入れ替えただけなので、1 2 3 と同等です。まず 4 を 2 つの部分 1 2 3 | 4 に分割し、次に 1 2 3 の順序を逆にして、次に 4 の順序を逆にして 3 2 1 4 を取得します。最後に全体の順序を逆にして、4 1 2 3 を取得します。
コードをコピーします。 コードは次のとおりです。
// バッファー内の開始と終了の間の要素の順序を逆にします
void Reverse( intbuffer[], int start, int end)
{
while ( start < end )
{
int temp =buffer[start++] ;
buffer[end--] = temp ;
}
// n 個の要素を含む配列バッファをk ビットずつ右に
void Shift ( intbuffer[], int n, int k )
{
k %= n ;

Reverse(buffer, n - k - 1) ; , n - 1 ) ;
Reverse(buffer, 0, n - 1);
}

文字列の順序を逆にする
n 個の要素を含む文字配列を与えて、それをその場で反転します。

おそらく、これは配列に関するものではなく、文字列に関するものだと思うでしょう。はい。ただし、質問ではインプレースの逆順序が必要であることを忘れないでください。つまり、追加のスペースの割り当ては許可されないため、文字列は変更できないため、パラメータは文字配列の形式でなければなりません（ここでは文字列のみです） C/C++ の定数) なので、これは配列に関連していますが、整数配列ではなく文字配列です。 2 つのポインタを使用して文字配列の最初の位置を指し、対応する文字を交換して、2 つのポインタが交差するまで配列の中心に向かって移動します。
コードをコピーします。 コードは次のとおりです。
// 文字列の逆順
void Reverse(char *a, int n)
{
int left = 0;
int right = n - 1; right)
{
char temp = a[left] ;
a[left++] = a[right] ;
}
}

n 個の要素を含む整数配列が与えられた場合a、そこから任意の m 個の要素を取り出し、すべての組み合わせを見つけます。たとえば、次の例:

a = 1, 2, 3, 4, 5
m = 3

出力:

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5
3 4 5

典型的な順列と組み合わせの問題では、問題を単純化するために、n 個の要素の値を設定することが推奨されます。それぞれ a ～ 1 ～ n。
コードをコピーする コードは次のとおりです:
//n m のすべての組み合わせを選択します
intbuffer[100];

void PrintArray(int *a, int n)
{
for (int i = 0; i < ; n; + +i)
cout
bool(int lastIndex, int value) int i = 0 ; i < lastIndex;
{
if (buffer[i] > = 値)
}
true を返す

void Select(int t, int n, int) m)
{
if (t == m)
PrintArray(buffer, m);
else
{
for (int i = 1; i <= n; i++)
{
buffer[t] = i;
if (IsValid (t, i))
Select(t + 1, n, m);
}
}
}

2 つの配列をマージする
n 個の要素を含む 2 つの順序付き (降順ではない) 整数配列 a と b が与えられた場合。 2 つの配列の要素を整数配列 c にマージし、重複する要素を削除し、c の順序を (降順ではなく) 保ちます。例は次のとおりです:

a = 1、2、4、8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8

マージソートの考え方を使用して、2 つのポインター i、j、k はそれぞれ配列 a と b を指します要素に対応するポインターのサイズには次の 3 つの状況があります:

a[i]
a[i] == b[j]、その場合、c[k] は a[ と等しくなります。 i] または b[j]。
a[i] > b[j]、その場合、c[k] = b[j]。
i または j が配列の末尾に達するまで上記のプロセスを繰り返し、残りの要素を配列 c に直接コピーします。
コードをコピーする コードは次のとおりです。
// 2 つの順序付けされた配列をマージします
void Merge(int *a, int *b, int *c, int n)
{
int i = 0;
int j = 0; int k = 0;

while (i < n && j < n)
{
if (a[i] < b[j])// a の要素が小さい場合は、その要素を a に挿入します。 into c
{
c[k++] = a[i] ;
}
else if (a[i] == b[j])// a 要素と b 要素が等しい場合、両方ともここに a を挿入します
{
c[k++] = a[i] ;
++j ;
else // a[i] > b が小さい場合、 b の要素を c に挿入します
{
c[k++] = b[j]
}
}

if (i == n) ; ,
{
for (int m = j; m c[k++] = b[m]
}
else//j == n の b 要素の残りの項目を処理します。 b を走査する場合、a を処理します
{
for (int m = i; m c[k++] = a[m]
}
}

並べ替え問題
与えられた n 個の要素 0 要素と 0 以外の要素を含む要素の整数配列 配列をソートするには、次の要件があります:

ソート後、すべての 0 要素が最初に来て、すべての非ゼロ要素が最後に来て、相対的な要素が続きます。非ゼロ要素の位置はソートの前後でも変わりません。
追加のストレージスペースは使用できません。
例は次のとおりです: 入力 0、3、0、2、1、0、0、出力 0、0、0、0、3、2、1。

このソートは、ソートの前後で非ゼロ要素の相対位置が変化しないことが必要なため、従来の意味でのソートではありません。おそらく、ソートと呼ぶ方が適切でしょう。配列全体を後ろから前にたどることができます。特定の位置 i の要素が 0 以外の要素である場合、a[k] が 0 の場合、a[i] は a[k] に代入され、a[ k]には値が割り当てられます。実際、i は非ゼロ要素の添字であり、k は 0 要素の添字です。
コードをコピーする コードは次のとおりです。
void Arrange(int* a, int n)
{
int k = n - 1;
for (int i = n - 1; i >= 0; --i)
{
if (a[i] != 0)
{
if (a[k] == 0)
{
a[k] = a[i]
} ; --k;
}
}