検索
ホームページバックエンド開発PHPチュートリアル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[左] }
int = 左 + (右 - 左) / 2 int leftmax ;
MaxandMin(a, left, mid , leftmax, leftmin) ;
int rightmin(a, rightmax, rightmin) ; leftmax > leftmax : rightmax ;
next = leftmax

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] 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 {
if(a[i] {
i++ ;
}
else // a[i] >= b[j]
{
if(b[j] {
j++ ;
else // b[ j] >= c[k]
{
if(c[k] {
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 {
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 {
int mid = (left + right) ;

if(a[mid] 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 {
if (a[ i] + b[j] ++i ;
else if (a[i] + b[j] == d)
{
cout ++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] 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] 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 {
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 cout
bool(int lastIndex, int value) int i = 0 ; i {
if (buffer[i] > = 値)
}
true を返す

void Select(int t, int n, int) m)
{
if (t == m)
PrintArray(buffer, m);
else
{
for (int i = 1; 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 {
if (a[i] {
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;
}
}

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
PHPロギング:PHPログ分析のベストプラクティスPHPロギング:PHPログ分析のベストプラクティスMar 10, 2025 pm 02:32 PM

PHPロギングは、Webアプリケーションの監視とデバッグ、および重要なイベント、エラー、ランタイムの動作をキャプチャするために不可欠です。システムのパフォーマンスに関する貴重な洞察を提供し、問題の特定に役立ち、より速いトラブルシューティングをサポートします

Laravelでフラッシュセッションデータを使用しますLaravelでフラッシュセッションデータを使用しますMar 12, 2025 pm 05:08 PM

Laravelは、直感的なフラッシュメソッドを使用して、一時的なセッションデータの処理を簡素化します。これは、アプリケーション内に簡単なメッセージ、アラート、または通知を表示するのに最適です。 データは、デフォルトで次の要求のためにのみ持続します。 $リクエスト -

PHPのカール:REST APIでPHPカール拡張機能を使用する方法PHPのカール:REST APIでPHPカール拡張機能を使用する方法Mar 14, 2025 am 11:42 AM

PHPクライアントURL(CURL)拡張機能は、開発者にとって強力なツールであり、リモートサーバーやREST APIとのシームレスな対話を可能にします。尊敬されるマルチプロトコルファイル転送ライブラリであるLibcurlを活用することにより、PHP Curlは効率的なexecuを促進します

Laravelテストでの簡略化されたHTTP応答のモッキングLaravelテストでの簡略化されたHTTP応答のモッキングMar 12, 2025 pm 05:09 PM

Laravelは簡潔なHTTP応答シミュレーション構文を提供し、HTTP相互作用テストを簡素化します。このアプローチは、テストシミュレーションをより直感的にしながら、コード冗長性を大幅に削減します。 基本的な実装は、さまざまな応答タイプのショートカットを提供します。 Illuminate \ support \ facades \ httpを使用します。 http :: fake([[ 'google.com' => 'hello world'、 'github.com' => ['foo' => 'bar']、 'forge.laravel.com' =>

Codecanyonで12の最高のPHPチャットスクリプトCodecanyonで12の最高のPHPチャットスクリプトMar 13, 2025 pm 12:08 PM

顧客の最も差し迫った問題にリアルタイムでインスタントソリューションを提供したいですか? ライブチャットを使用すると、顧客とのリアルタイムな会話を行い、すぐに問題を解決できます。それはあなたがあなたのカスタムにより速いサービスを提供することを可能にします

PHPにおける後期静的結合の概念を説明します。PHPにおける後期静的結合の概念を説明します。Mar 21, 2025 pm 01:33 PM

記事では、PHP 5.3で導入されたPHPの後期静的結合(LSB)について説明し、より柔軟な継承を求める静的メソッドコールのランタイム解像度を可能にします。 LSBの実用的なアプリケーションと潜在的なパフォーマ

フレームワークのカスタマイズ/拡張:カスタム機能を追加する方法。フレームワークのカスタマイズ/拡張:カスタム機能を追加する方法。Mar 28, 2025 pm 05:12 PM

この記事では、フレームワークにカスタム機能を追加し、アーキテクチャの理解、拡張ポイントの識別、統合とデバッグのベストプラクティスに焦点を当てています。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser は、オンライン試験を安全に受験するための安全なブラウザ環境です。このソフトウェアは、あらゆるコンピュータを安全なワークステーションに変えます。あらゆるユーティリティへのアクセスを制御し、学生が無許可のリソースを使用するのを防ぎます。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

このプロジェクトは osdn.net/projects/mingw に移行中です。引き続きそこでフォローしていただけます。 MinGW: GNU Compiler Collection (GCC) のネイティブ Windows ポートであり、ネイティブ Windows アプリケーションを構築するための自由に配布可能なインポート ライブラリとヘッダー ファイルであり、C99 機能をサポートする MSVC ランタイムの拡張機能が含まれています。すべての MinGW ソフトウェアは 64 ビット Windows プラットフォームで実行できます。

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません