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 ? : 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[l]
}
int m = (l + r) ; ; // 中間点を求める

int lmax // 左半分の最大値
int lmin // 左半分の最小値
MaxandMin(a, l, m, lmax, lmin);左半分

int rmax; // 右半分の最大値
int rmin // 右半分の最小値
MaxandMin(a, m + 1, r, rmax, rmin);右半分

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



次の最大値と 2 番目の最大値を求めます。配列
n 個の要素を含む配列を指定した整数配列で、その最大値と 2 番目の最大値を見つけます。

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

コードをコピーします

コードは次のとおりです:

/ / 配列 Value の最大値と 2 番目に大きい値を検索します。戻り値は最大値と秒値にあります void MaxandMin(int *a, int left, int right, int &max, int &second) { if(left == right ) {

max = a[左] ;

2番目 = a[左] ;
else if(左 + 1 == 右)
{
最大 = a[左] >左] : a[右] ;
秒 = a [左] < a[左] : a[右]
}
int 中央 = 左 + (右 - 左) / 2 ;

int leftmin ;
int rightmin(a、mid + 1、rightmax、rightmin);

max = leftmax > leftmax : rightmax ;
Second = leftmax < rightmax : rightmax ;



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

現在の値と現在の値のカウンターを設定し、現在の値を配列の最初の要素に初期化します。カウンター値は 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 カウント = 1;

for (int i = 1; i


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

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

まず配列をソートし、次にそれを 1 回走査します:

コードをコピーします コードは次のとおりです:

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) ; int i ; // 数値 1 のインデックス

int minDistance = numeric_limits
for (int k = 0; k < n - 1; + +k)
{
if (a[k + 1] - a[k] < minDistance)
{
minDistance = a[k + 1] - a[k] ; = a[k + 1] ;

cout <int j = 0 ; while (i if (a[i] ++i ; ] == b [j])

cout <++i ;
else// a[i] > j]
+ +j ;
}
}



たとえば、a には n 個の要素があるため、a の任意の要素に対して二分探索を実行します。 b. バイナリ検索にはログインが必要です。したがって、すべての同じ要素を見つける時間計算量は 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 ] < ; b[j])
{
i++ ;
}

else // a[i] >= b[j] { if(b[j] < c[k]) j++ ; }

else // b[j] >= c[k]

{
if(c[k] {
}
else // c[k] > ;= a[i]
{
cout <}
}

<< ; endl ;
}



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 の要素はすべて、a で二分検索されます。

コードをコピーします コードは次のとおりです:

// 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] ; (bb, 0 , n) ;

bool *bc = new bool[n] ;
memset(bb, 0, n) ; a で BS を実行し、すべての共通要素をマークします要素
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; left <= right)
{
int mid = (left + right) ;

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

return false ;

// 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 つのポインターが交差するまで同時に両端から中央まで移動します。



コードをコピーします。は次のとおりです:


// 定和を持つ数値のペアを調べます

voidFixedSum(int* a, int* b, int n, int d) { for (int i = 0, j = n - 1; i = 0) if (a[i] + b[j] < d) else if (a[i] + b[j] ] == d)

cout <else // a[i] + b[j] > d
--j ;
}
}


サブセグメントの最大合計
整数配列 a が与えられた場合、最大の連続サブセグメントの合計を求めます。 sum は負の数であり、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) ; ;
}


最大サブセグメント積
整数 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 = maxProduct = max(minProduct * a[i], 1); * a[i ];
}

r = max(r, maxProduct);
}


配列循環シフト
n 要素を含む配列を右に循環移動するには複雑な時間が必要です次数は 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[ start++ ] = temp ; // バッファn 個の要素を含む配列 k ビットを右にシフトします void Shift( intbuffer[], int n, int k )

{

k %= n ;

Reverse(buffer, 0, n - k - 1) ; , n - k , 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;
while ( left < 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 < ++i)
cout <{
for (int i = 0; i < lastIndex; i++)
{
if (buffer[i] > = value)

return false } return true }

void Select( int t, int n, int m)

{
if (t == m)
PrintArray(buffer, m)
else
{
for (int i = 1; i {
;バッファ[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 を指し、2 つのポインターに対応する要素のサイズを比較します。

a[i]
a[i] == の 3 つの状況があります。 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 ; を挿入します。 b[j] / / b の要素が小さい場合は、b の要素を c に挿入します
{
c[k++] = b[j]
++j ;

if (i == n) // a が Completed を通過する場合、b の残りの要素を処理します
{
for (int m = j; m c[k++] = b[m]
else/ ; /j == n、b がトラバースされる場合、a の残りの要素を処理します
{
for (int m = i; m c[k++] = a[m]
;


繰り返しソート問題
0 個の要素と 0 以外の要素を含む n 個の要素を含む整数配列 a が与えられた場合、配列をソートします。

ソート後、すべての 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] ; ] = 0
}
--k
}
}






http://www.bkjia.com/PHPjc/323992.html

www.bkjia.com

tru​​e

http://www.bkjia.com/PHPjc/323992.html

技術記事

配列の合計 n 個の要素を含む整数配列 a が与えられた場合、a 内のすべての要素の合計を求めます。もしかしたら、とても単純なことだと思うかもしれません、確かに単純ですが、それでもなぜそう言うのですか?理由は 2 つあります...