Write a Method That Reads the Elements of an Array of Integers Until a Value of -100 Is Found.

Chapter 7  Arrays and References

Upwardly to this signal, the but variables we have used were for individual values such equally numbers or strings. In this chapter, you'll learn how to store multiple values of the same type by using a unmarried variable. This language feature will enable you to write programs that dispense larger amounts of data.

For case, Practice 5 asked you to check whether every letter in a string appears exactly twice. One algorithm (which hopefully you already discovered) loops through the string 26 times, once for each lowercase letter:

// outer loop: for each lowercase letter for (char c = 'a'; c <= 'z'; c++) { // inner loop: count how many times the letter appears for (int i = 0; i < str.length(); i++) { ... // if the count is not 0 or two, return false

This "nested loops" approach is inefficient, specially when the string is long. For example, there are more than 3 million characters in War and Peace; to process the whole book, the nested loop would run well-nigh 80 million times.

Some other algorithm would initialize 26 variables to zero, loop through the string one time, and utilise a giant if argument to update the variable for each letter. But who wants to declare 26 variables?

That's where arrays come in. We can use a single variable to store 26 integers. Rather than use an if argument to update each value, we can utilise arithmetic to update the northth value directly. We will present this algorithm at the end of the affiliate.

7.1  Creating Arrays

An array is a sequence of values; the values in the array are called elements. Y'all can make an assortment of int s, double s, Strings, or any other type, only all the values in an array must accept the same type.

To create an assortment, you have to declare a variable with an array blazon so create the assortment itself. Array types look like other Java types, except they are followed by square brackets ([]). For example, the following lines declare that counts is an "integer array" and values is a "double array":

int[] counts; double[] values;

To create the array itself, you have to use the new operator, which yous first saw in Department 3.2. The new operator allocates memory for the assortment and automatically initializes all of its elements to zero:

counts = new int[four]; values = new double[size];

The first assignment makes counts refer to an array of four integers. The 2d makes values refer to an array of double southward, but the number of elements depends on the value of size (at the time the array is created).

Of form, yous tin as well declare the variable and create the array with a single line of lawmaking:

int[] counts = new int[4]; double[] values = new double[size];

Yous tin can use whatever integer expression for the size of an assortment, as long as the value is nonnegative. If yous endeavor to create an array with -4 elements, for case, y'all volition get a NegativeArraySizeException. An array with zero elements is allowed, and at that place are special uses for such arrays.

You lot tin can initialize an array with a comma-separated sequence of elements enclosed in braces, like this:

This statement creates an array variable, a, and makes it refer to an array with 4 elements.

7.2  Accessing Elements

When yous create an array with the new operator, the elements are initialized to naught. Figure 7.1 shows a memory diagram of the counts array so far.

Figure vii.i: Memory diagram of an int array.

The pointer indicates that the value of counts is a reference to the array. You should think of the array and the variable that refers to it equally ii dissimilar things. As y'all'll soon meet, we can assign a unlike variable to refer to the aforementioned array, and we tin change the value of counts to refer to a unlike array.

The boldface numbers inside the boxes are the elements of the array. The lighter numbers outside the boxes are the indexes used to identify each location in the array. As with strings, the index of the first element is 0, not 1. For this reason, we sometimes refer to the first chemical element as the "zeroth" element.

The [] operator selects elements from an array:

System.out.println("The zeroth element is " + counts[0]);

You tin can apply the [] operator anywhere in an expression:

counts[0] = 7; counts[ane] = counts[0] * 2; counts[2]++; counts[3] -= sixty;

Figure 7.2 shows the upshot of these statements.

Figure seven.two: Memory diagram afterwards several consignment statements.

Yous tin employ any expression every bit an alphabetize, as long as it has type int . I of the nigh common means to index an array is with a loop variable. For example:

int i = 0; while (i < iv) { Organization.out.println(counts[i]); i++; }

This while loop counts up from 0 to iv. When i is 4, the condition fails and the loop terminates. So the body of the loop is executed only when i is 0, one, 2, or 3. In this context, the variable name i is short for "index".

Each time through the loop, we use i as an index into the array, displaying the ithursday element. This type of array processing is usually written as a for loop:

for (int i = 0; i < four; i++) { System.out.println(counts[i]); }

For the counts array, the but legal indexes are 0, 1, 2, and 3. If the alphabetize is negative or greater than 3, the effect is an ArrayIndexOutOfBoundsException.

seven.3  Displaying Arrays

You tin use println to display an array, merely it probably doesn't do what you would like. For example, say you lot print an array like this:

int[] a = {1, 2, 3, 4}; System.out.println(a);

The output is something like this:

The bracket indicates that the value is an assortment, I stands for "integer", and the balance represents the accost of the array in memory.

If nosotros want to display the elements of the array, we can do it ourselves:

public static void printArray(int[] a) { System.out.print("{" + a[0]); for (int i = 1; i < a.length; i++) { Arrangement.out.print(", " + a[i]); } Organization.out.println("}"); }

Given the previous assortment, the output of printArray is as follows:

The Java library includes a class, java.util.Arrays, that provides methods for working with arrays. One of them, toString, returns a cord representation of an array. After importing Arrays, nosotros can invoke toString like this:

System.out.println(Arrays.toString(a));

And the output is shown here:

Notice that Arrays.toString uses foursquare brackets instead of curly braces. But it beats writing your own printArray method.

vii.iv  Copying Arrays

Equally explained in Section 7.ii, assortment variables contain references to arrays. When yous make an assignment to an assortment variable, it simply copies the reference. But it doesn't copy the array itself. For example:

double[] a = new double[3]; double[] b = a;

These statements create an assortment of three double due south and make two dissimilar variables refer to it, every bit shown in Figure 7.iii.

Figure 7.3: Retentivity diagram of two variables referring to the same array.

Whatever changes made through either variable will be seen by the other. For example, if we set up a[0] = 17.0, and then display b[0], the outcome is 17.0. Because a and b are unlike names for the same thing, they are sometimes chosen aliases.

If you actually want to copy the assortment, not just the reference, you have to create a new array and copy the elements from one to the other, like this:

double[] b = new double[3]; for (int i = 0; i < 3; i++) { b[i] = a[i]; }

java.util.Arrays provides a method named copyOf that performs this task for you. Then you can replace the previous code with one line:

double[] b = Arrays.copyOf(a, 3);

The 2nd parameter is the number of elements you want to copy, so copyOf can too be used to copy part of an array. Figure 7.4 shows the land of the assortment variables later on invoking Arrays.copyOf.

Figure vii.4: Memory diagram of two variables referring to dissimilar arrays.

The examples so far piece of work only if the array has three elements. It is ameliorate to generalize the code to work with arrays of any size. We can practice that by replacing the magic number, 3, with a.length:

double[] b = new double[a.length]; for (int i = 0; i < a.length; i++) { b[i] = a[i]; }

All arrays accept a built-in abiding, length, that stores the number of elements. In contrast to Cord.length(), which is a method, a.length is a abiding. The expression a.length may expect like a method invocation, but there are no parentheses and no arguments.

The last time the loop gets executed, i is a.length - ane, which is the index of the last element. When i is equal to a.length, the status fails and the body is not executed—which is a good thing, considering trying to access a[a.length] would throw an exception.

Of course, we can supercede the loop altogether by using Arrays.copyOf and a.length for the second statement. The post-obit line produces the same event shown in Figure seven.4:

double[] b = Arrays.copyOf(a, a.length);

The Arrays class provides many other useful methods like Arrays.compare, Arrays.equals, Arrays.fill, and Arrays.sort. Accept a moment to read the documentation by searching the web for coffee.util.Arrays.

7.five  Traversing Arrays

Many computations tin exist implemented by looping through the elements of an array and performing an operation on each element. Looping through the elements of an assortment is called a traversal:

int[] a = {1, 2, 3, four, 5}; for (int i = 0; i < a.length; i++) { a[i] *= a[i]; }

This example traverses an array and squares each chemical element. At the end of the loop, the assortment has the values {one, iv, 9, 16, 25}.

Another common blueprint is a search, which involves traversing an array and "searching" for a item element. For example, the following method takes an assortment and a value, and information technology returns the index where the value appears:

public static int search(double[] assortment, double target) { for (int i = 0; i < assortment.length; i++) { if (assortment[i] == target) { return i; } } return -one; // not found }

If we find the target value in the array, we return its index immediately. If the loop exits without finding the target, it returns -1, a special value chosen to bespeak a failed search. (This code is substantially what the String.indexOf method does.)

The following code searches an array for the value 1.23, which is the third element. Because assortment indexes start at 0, the output is two:

double[] array = {3.fourteen, -55.0, 1.23, -0.viii}; int alphabetize = search(array, i.23); System.out.println(index);

Another common traversal is a reduce functioning, which "reduces" an array of values downward to a single value. Examples include the sum or product of the elements, the minimum, and the maximum. The following method takes an array and returns the sum of its elements:

public static double sum(double[] array) { double total = 0.0; for (int i = 0; i < assortment.length; i++) { total += array[i]; } return total; }

Before the loop, we initialize total to 0. Each time through the loop, we update total by adding 1 element from the assortment. At the end of the loop, total contains the sum of the elements. A variable used this way is sometimes called an accumulator, considering it "accumulates" the running full.

7.6  Random Numbers

Near estimator programs do the same matter every time they run; programs similar that are called deterministic. Usually, determinism is a proficient thing, since we expect the same calculation to yield the same result. But for some applications, nosotros desire the estimator to be unpredictable. Games are an obvious example, but there are many others, like scientific simulations.

Making a programme nondeterministic turns out to be hard, because it'due south incommunicable for a computer to generate truly random numbers. Just there are algorithms that generate unpredictable sequences chosen pseudorandom numbers. For about applications, they are as good as random.

If you did Practice four, yous take already seen coffee.util.Random, which generates pseudorandom numbers. The method nextInt takes an integer statement, n, and returns a random integer between 0 and n - 1 (inclusive).

If yous generate a long serial of random numbers, every value should appear, at least approximately, the same number of times. One manner to test this behavior of nextInt is to generate a large number of values, store them in an array, and count the number of times each value occurs.

The post-obit method creates an int array and fills it with random numbers between 0 and 99. The argument specifies the desired size of the array, and the return value is a reference to the new assortment:

public static int[] randomArray(int size) { Random random = new Random(); int[] a = new int[size]; for (int i = 0; i < a.length; i++) { a[i] = random.nextInt(100); } return a; }

The following master method generates an array and displays it by using the printArray method from Department 7.3. We could accept used Arrays.toString, simply we like seeing curly braces instead of square brackets:

public static void chief(String[] args) { int[] array = randomArray(eight); printArray(array); }

Each time you run the programme, you should get unlike values. The output will look something similar this:

{fifteen, 62, 46, 74, 67, 52, 51, ten}

7.7  Building a Histogram

If these values were test scores—and they would exist pretty bad exam scores in that example—the instructor might present them to the course in the class of a histogram. In statistics, a histogram is a prepare of counters that keeps track of the number of times each value appears.

For test scores, we might have 10 counters to keep rail of how many students scored in the 90s, the 80s, etc. To practise that, we can traverse the array and count the number of elements that fall in a given range.

The post-obit method takes an array and 2 integers. Information technology returns the number of elements that fall in the range from depression to high - ane:

public static int inRange(int[] a, int low, int loftier) { int count = 0; for (int i = 0; i < a.length; i++) { if (a[i] >= low && a[i] < high) { count++; } } return count; }

This pattern should look familiar: it is another reduce operation. Notice that depression is included in the range (>=), but high is excluded (<). This design keeps u.s.a. from counting any scores twice.

Now nosotros tin count the number of scores in each form range. We add the post-obit code to our master method:

int[] scores = randomArray(30); int a = inRange(scores, 90, 100); int b = inRange(scores, 80, 90); int c = inRange(scores, 70, 80); int d = inRange(scores, sixty, 70); int f = inRange(scores, 0, 60);

This code is repetitive, but it is acceptable as long as the number of ranges is small-scale. Suppose nosotros wanted to go along rail of the number of times each individual score appears. Then we would have to write 100 lines of code:

int count0 = inRange(scores, 0, ane); int count1 = inRange(scores, ane, two); int count2 = inRange(scores, 2, 3); ... int count99 = inRange(scores, 99, 100);

What we demand is a way to store 100 counters, preferably so we can employ an index to access them. Expect a minute—that's exactly what an array does.

The following fragment creates an array of 100 counters, i for each possible score. It loops through the scores and uses inRange to count how many times each score appears. Then it stores the results in the counts array:

int[] counts = new int[100]; for (int i = 0; i < counts.length; i++) { counts[i] = inRange(scores, i, i + ane); }

Notice that we are using the loop variable i three times: as an index into the counts array, and in the final ii arguments of inRange.

The code works, merely it is not equally efficient as it could be. Every fourth dimension the loop invokes inRange, it traverses the entire array. It would be better to brand a single pass through the scores assortment.

For each score, nosotros already know which range it falls in—the score itself. We tin apply that value to increase the corresponding counter. This code traverses the array of scores only in one case to generate the histogram:

int[] counts = new int[100]; for (int i = 0; i < scores.length; i++) { int index = scores[i]; counts[index]++; }

Each time through the loop, it selects 1 element from scores and uses information technology as an index to increment the corresponding element of counts. Considering this code traverses the array of scores just once, it is much more efficient.

7.8  The Enhanced for Loop

Since traversing arrays is so common, Java provides an alternative syntax that makes the code more meaty. Consider a for loop that displays the elements of an assortment on divide lines:

for (int i = 0; i < values.length; i++) { int value = values[i]; Organization.out.println(value); }

We could rewrite the loop like this:

for (int value : values) { Organisation.out.println(value); }

This argument is called an enhanced for loop, besides known equally the "for each" loop. You can read the lawmaking as, "for each value in values". It's conventional to utilise plural nouns for assortment variables and singular nouns for element variables.

Find how the single line for (int value : values) replaces the first two lines of the standard for loop. It hides the details of iterating each alphabetize of the assortment, and instead, focuses on the values themselves.

Using the enhanced for loop, and removing the temporary variable, we tin write the histogram lawmaking from the previous section more concisely:

int[] counts = new int[100]; for (int score : scores) { counts[score]++; }

Enhanced for loops ofttimes make the code more than readable, especially for accumulating values. Only they are not helpful when you lot need to refer to the index, as in search operations:

for (double d : array) { if (d == target) { // assortment contains d, simply we don't know where } }

7.9  Counting Characters

We now return to the case from the beginning of the affiliate and nowadays a solution to Exercise 5 using arrays. Here is the problem again:

A give-and-take is said to be a "doubloon" if every letter that appears in the word appears exactly twice. Write a method called isDoubloon that takes a string and checks whether it is a doubloon. To ignore case, invoke the toLowerCase method earlier checking.

Based on the approach from Section 7.7, we will create an array of 26 integers to count how many times each letter of the alphabet appears. Nosotros convert the string to lowercase, so that we can treat 'A' and 'a' (for instance) as the same alphabetic character.

int[] counts = new int[26]; Cord lower = s.toLowerCase();

We can utilise a for loop to iterate each character in the string. To update the counts array, nosotros need to compute the alphabetize that corresponds to each grapheme. Fortunately, Java allows you to perform arithmetics on characters:

for (int i = 0; i < lower.length(); i++) { char letter = lower.charAt(i); int alphabetize = letter - 'a'; counts[alphabetize]++; }

If letter is 'a' , the value of alphabetize is 0; if letter of the alphabet is 'b' , the value of index is 1, and and then on.

And then nosotros utilize index to increment the respective element of counts. At the end of the loop, counts contains a histogram of the messages in the cord lower.

We can simplify this lawmaking with an enhanced for loop, simply it doesn't piece of work with strings; nosotros accept to convert lower to an array of characters, similar this:

for (char alphabetic character : lower.toCharArray()) { int index = alphabetic character - 'a'; counts[alphabetize]++; }

In one case nosotros have the counts, nosotros can use a 2d for loop to cheque whether each letter appears zero or two times:

for (int count : counts) { if (count != 0 && count != 2) { render false; // not a doubloon } } return true; // is a doubloon

If we detect a count that is neither 0 or 2, we know the word is not a doubloon and we can return immediately. If we go far all the mode through the for loop, we know that all counts are 0 or ii, which ways the discussion is a doubloon.

Pulling together the code fragments, and calculation some comments and test cases, here'south the unabridged program:

This example uses methods, if statements, for loops, arithmetics and logical operators, integers, characters, strings, booleans, and arrays. We hope y'all'll take a second to capeesh how much you've learned!

7.10  Vocabulary

array:

A collection of values in which all the values have the same type, and each value is identified by an index.

chemical element:

One of the values in an array. The [] operator selects elements.

index:

An integer variable or value used to bespeak an element of an assortment.

allocate:

To reserve memory for an assortment or other object. In Java, the new operator allocates retentiveness.

reference:

A value that indicates a storage location. In a memory diagram, a reference appears as an arrow.

allonym:

A variable that refers to the same object as another variable.

traversal:

Looping through the elements of an assortment (or other collection).

search:

A traversal pattern used to find a particular element of an array.

reduce:

A traversal pattern that combines the elements of an assortment into a single value.

accumulator:

A variable used to accumulate results during a traversal.

deterministic:

A program that does the aforementioned thing every time it is run.

nondeterministic:

A program that always behaves differently, fifty-fifty when run multiple times with the same input.

pseudorandom:

A sequence of numbers that appear to be random but are really the production of a deterministic ciphering.

histogram:

An array of integers in which each integer counts the number of values that fall into a certain range.

enhanced for loop:

An culling syntax for traversing the elements of an array (or other drove).

7.11  Exercises

The lawmaking for this affiliate is in the ch07 directory of ThinkJavaCode2. See folio ?? for instructions on how to download the repository. Earlier you showtime the exercises, we recommend that y'all compile and run the examples.

If you lot haven't already, take a wait at Appendix D, where we've collected some of our favorite debugging communication. It refers to language features we haven't yet covered, but it's practiced for you to know what's available when you need information technology.

Do one

The purpose of this practise is to practice reading lawmaking and recognizing the traversal patterns in this chapter. The post-obit methods are hard to read, because instead of using meaningful names for the variables and methods, they utilize names of fruit.

For each method, write 1 sentence that describes what the method does, without getting into the details of how it works. And for each variable, identify the role it plays.

public static int assistant(int[] a) { int kiwi = 1; int i = 0; while (i < a.length) { kiwi = kiwi * a[i]; i++; } return kiwi; }

public static int grapefruit(int[] a, int grape) { for (int i = 0; i < a.length; i++) { if (a[i] == grape) { return i; } } return -ane; }

public static int pineapple(int[] a, int apple) { int pear = 0; for (int pine: a) { if (pine == apple) { pear++; } } render pear; }

Practise 2

What is the output of the post-obit program? Describe in a few words what mus does. Draw a stack diagram just earlier mus returns.

public static int[] brand(int n) { int[] a = new int[n]; for (int i = 0; i < north; i++) { a[i] = i + 1; } return a; }

public static void dub(int[] jub) { for (int i = 0; i < jub.length; i++) { jub[i] *= two; } }

public static int mus(int[] zoo) { int fus = 0; for (int i = 0; i < zoo.length; i++) { fus += zoo[i]; } return fus; }

public static void main(String[] args) { int[] bob = make(five); dub(bob); System.out.println(mus(bob)); }

Exercise 3

Write a method called indexOfMax that takes an array of integers and returns the index of the largest chemical element. Tin can you write this method by using an enhanced for loop? Why or why non?

Practice iv

The Sieve of Eratosthenes is "a simple, ancient algorithm for finding all prime numbers up to whatever given limit" ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ).

Write a method chosen sieve that takes an integer parameter, n, and returns a boolean assortment that indicates, for each number from 0 to n - 1, whether the number is prime number.

Exercise 5

Write a method named areFactors that takes an integer n and an array of integers, and returns truthful if the numbers in the array are all factors of n (which is to say that n is divisible by all of them).

Exercise 6

Write a method named arePrimeFactors that takes an integer n and an array of integers, and that returns true if the numbers in the array are all prime and their production is north.

Exercise seven

Write a method called letterHist that takes a string every bit a parameter and returns a histogram of the letters in the cord. The zeroth element of the histogram should contain the number of a's in the string (upper- and lowercase); the 25th element should incorporate the number of z's. Your solution should traverse the string but once.

Exercise 8

Two words are anagrams if they comprise the same letters and the aforementioned number of each letter. For instance, "stop" is an anagram of "pots", "allen downey" is an anagram of "well bellyaching", and "christopher mayfield" is an anagram of "how-do-you-do prof the camel is dry". Write a method that takes two strings and checks whether they are anagrams of each other.

ferrisvemook82.blogspot.com

Source: https://books.trinket.io/thinkjava2/chapter7.html

Share this post