An example Analysis of Java Product problem

This article introduces the relevant knowledge of "Java product problem example analysis". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Interview questions: turn things upside down

In a binary search tree, two nodes are reversed. It is required to implement an algorithm to restore the correct binary search tree without changing the tree structure. It is easy to give an implementation of space O (n), so how to give an implementation of space O (1)?

Product analysis of selflessness

Title:

Give you an array A [1. N], please construct a new array B [1. N] in O (n) time, such that B [I] = A [1] * A [2] *. * A [n] / A [I]. You can't use division.

Analysis:

When you see the question, don't be nervous, be clear-headed and see through the interviewer's original intention. In fact, he is using the formula of division, but he asks you not to use division to confuse you.

Requires that B [I] = A [0] * be calculated without division. * A [n] / A [I], you can get B [I] = A [0] * by simply changing the form. * A [I-1] * A [I + 1] * … * A [n], a total of 1 times multiplication. Each B [I] is calculated, and the total time complexity is O (n ^ 2). Do not meet the requirements of the topic, the number of multiplication must be reduced. How to reduce the number of multiplication? Continue to analyze, through the above transformation, we can find that B [I] is obtained by multiplying two parts:

A [0] *... * A [I-1] A [ionization 1] *... * A [n]

Let's first look at the * * part. When calculating B [I], we can use the * * part of B [I]. You only need to multiply A [I] to get the * * part of B [I].

The second part is the same, after calculating A [item1] *. * A [n], and then calculate A [I] * A [I + 1] * … * A [n], just multiply by A [I]. A [I] * A [I + 1] *... * A [n] is the second part of B [I-1].

Based on this analysis, two new arrays are constructed: C and D (two arrays are used for convenient explanation).

C [I] = A [0] *... * A [I-1] = C [I-1] * A [I-1] D [I] = A [I-1] * … * A [n] = D [ionization 1] * A [iatro1}

Building C and D is the time complexity of O (n) (C traverses the array from front to back, D traverses one side of the array from back to front), then B [I] = C [I] * D [I] is also the time complexity of O (n). The time complexity of the whole algorithm is O (n).

This is the end of the question.

But the interviewer's question is not finished, they will continue to ask, the space of this solution is O (n), can it be realized in the case of space O (1)?

First look at an array of only five numbers, A [1], A [2], A [3], A [4], A [5].

First, traverse from beginning to end:

B [1] = A [1] B [2] = B [1] * A [2] B [3] = B [2] * A [3] B [4] = B [3] * A [4] B [5], temporary variable Centra [5]

Then traverse from end to end:

B [4] = B [3] * C, C=C*A [4] B [3] = B [2] * C, C=C*A [3] B [2] = B [1] * C, C=C*A [2] B [1] = C

Through this small example, we get the algorithm, which can be extended to any number of elements. This is a common technique in interviews.

This is the end of the content of "example Analysis of Java Product". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!