This article will introduce to you how to implement the function of random, no repetitive numbers in JAVA. If you are a beginner, it is necessary to read this article, because this feature will generally be encountered during interviews. Including when I recruit people, I also like to ask others about this question, mainly to see how the model and basic knowledge of the problem are considered.
I hope this article can help friends who are in contact for the first time, because I have contacted some friends who either cannot write it or use a very flat way of thinking to achieve it.
Generally, friends with some development experience can implement such functions, but it is just a matter of efficiency. When we face such problems, we always think of it in a straight order, and then add random numbers to the array in a loop. In the process of adding numbers, first look for whether this number exists in the array. If this number does not exist, it will be added directly to the array; if this number exists, it will not be added. We usually consider the problem in this way, and we can implement functions in this way. As I said just now, it is just a matter of efficiency.
In order to better understand the meaning of this question, let's first look at the specific content: generate a random array of 1-100, but the numbers in the array cannot be repeated, that is, the positions are random, but the elements of the array cannot be repeated.
Here, we have not specified the length of the array, we can make it any length between 1-100.
Next, let’s take a look at several implementation methods and compare these methods .
Usually we will use ArrayList or array to implement it. Let’s first look at the implementation process of ArrayList, as shown in the following code:
import java.util.ArrayList;import java.util.Random;/** * Implementation using ArrayList* @Description: * @File: Demo.java * @Package None * @Author Hanyonglu * @Date 2012-10-18 06:16:55 pm * @Version V1.0 */public class Demo { public static void main(String[] args) { Object[] values = new Object[20]; Random random = new Random(); ArrayList<Integer> list = new ArrayList<Integer>(); for(int i = 0; i < values.length;i++){ int number = random.nextInt(100) + 1; if(!list.contains(number)){ list.add(number); } } values = list.toArray(); // traverse the array and print the data for(int i = 0;i < values.length;i++){ System.out.print(values[i] + "/t"); if(( i + 1 ) % 10 == 0){ System.out.println("/n"); } } }} The process of implementing using arrays is as follows:
import java.util.Random;/** * Implementation using arrays * @Description: * @File: Demo4.java * @Package None * @Author Hanyonglu * @Date 2012-10-18 06:27:38 pm * @Version V1.0 */public class Demo4 { public static void main(String[] args) { int[] values = new int[20]; Random random = new Random(); for(int i = 0;i < values.length;i++){ int number = random.nextInt(100) + 1; for(int j = 0;j <= i;j++){ if(number != values[j]){ values[i]=number; } } } // traverse the array and print the data for(int i = 0;i < values.length;i++){ System.out.print(values[i] + "/t"); if(( i + 1 ) % 10 == 0){ System.out.println("/n"); } } }} The above two implementation processes are relatively inefficient. Because every time you add, you have to traverse whether this number exists in the current list, the time complexity is O(N^2). We can think about it this way: Since there is no duplication involved, we can think about the functions of HashSet and HashMap. HashSet implements the Set interface, and the mathematical definition of Set is a set without duplication and order. HashMap implements Map, and it is also a key that does not allow duplicates. This way we can use HashMap or HashSet to achieve it.
When using HashMap implementation, you only need to convert its key into an array and it will be OK, as follows:
import java.util.HashMap;import java.util.Iterator;import java.util.Random;import java.util.Map.Entry;/** * Implementation using HashMap* @Description: * @File: Demo.java * @Package None * @Author Hanyonglu * @Date 2012-10-18 06:12:50 pm * @Version V1.0 */public class Demo { public static void main(String[] args) { int n = 0; Object[] values = new Object[20]; Random random = new Random(); HashMap<Object, Object> hashMap = new HashMap<Object, Object>(); // Generate random numbers and store HashMap for(int i = 0;i < values.length;i++){ int number = random.nextInt(100) + 1; hashMap.put(number, i); } // Import array values from HashMap values = hashMap.keySet().toArray(); // traverse the array and print data for(int i = 0;i < values.length;i++){ System.out.print(values[i] + "/t"); if(( i + 1 ) % 10 == 0){ System.out.println("/n"); } } // Iterator iter = hashMap.entrySet().iterator();// // traversal HashMap// while (iter.hasNext()) {// Entry<Integer, Integer> entry = (Entry)iter.next();// int key = entry.getKey();// n++;// // System.out.print(key + "/t");// // if(n % 10 == 0){// System.out.println("/n");// }// } }} Since the relationship between HashSet and HashMap is too close, HashSet is implemented using HashMap at the bottom, but there is no collection of Value and only one collection of Keys, so it can also be implemented using HashSet, as follows:
import java.util.HashSet;import java.util.Random;/** * Implementation using HashSet* @Description: * @File: Test.java * @Package None * @Author Hanyonglu * @Date 2012-10-18 06:11:41 pm * @Version V1.0 */public class Test { public static void main(String[] args) { Random random = new Random(); Object[] values = new Object[20]; HashSet<Integer> hashSet = new HashSet<Integer>(); // Generate random numbers and store HashSet for(int i = 0;i < values.length;i++){ int number = random.nextInt(100) + 1; hashSet.add(number); } values = hashSet.toArray(); // traverse the array and print data for(int i = 0;i < values.length;i++){ System.out.print(values[i] + "/t"); if(( i + 1 ) % 10 == 0){ System.out.println("/n"); } } }} This is a little more efficient. If we have limited the length of the array, we just need to transform the for loop and set it to a whlie loop. As shown below:
import java.util.HashSet;import java.util.Random;/** * Implementation using HashSet* @Description: * @File: Test.java * @Package None * @Author Hanyonglu * @Date 2012-10-18 05:11:41 pm * @Version V1.0 */public class Test { public static void main(String[] args) { Random random = new Random(); Object[] values = new Object[20]; HashSet<Integer> hashSet = new HashSet<Integer>(); // Generate random numbers and store HashSet while(hashSet.size() < values.length){ hashSet.add(random.nextInt(100) + 1); } values = hashSet.toArray(); // traverse the array and print the data for(int i = 0;i < values.length;i++){ System.out.print(values[i] + "/t"); if(( i + 1 ) % 10 == 0){ System.out.println("/n"); } } }}We can set the length of the array to 100 and check the running effect as shown in the figure below:
Compared with the above, using HashMap is relatively efficient. In fact, it is a HashSet, an array, and finally an ArrayList. If we generate 10000 data, we will find that using HashMap takes time: 0.05s, HashSet is 0.07s, array is 0.20s, and ArrayList is 0.25s. If you are interested, you can set the time to check it out.
Of course, in addition to using HashMap implementation, there are other efficient methods. For example, we can store numbers 1-100 in an array, and then randomly generate two subscripts in the for loop. If these two subscripts are not equal, we can exchange elements in the array. The implementation process is as follows:
import java.util.Random;/** * Random position conversion implementation* @Description: * @File: Demo4.java * @Package None * @Author Hanyonglu * @Date 2012-10-18 06:54:06 pm * @Version V1.0 */public class Demo4 { public static void main(String[] args) { int values[] = new int[100]; int temp1,temp2,temp3; Random r = new Random(); for(int i = 0;i < values.length;i++){ values[i] = i + 1; } //Randomly exchange values.length times for(int i = 0;i < values.length;i++){ temp1 = Math.abs(r.nextInt()) % (values.length-1); //Randomly generate one position temp2 = Math.abs(r.nextInt()) % (values.length-1); //Randomly generate another position if(temp1 != temp2){ temp3 = values[temp1]; values[temp1] = values[temp2]; values[temp2] = temp3; } } // traverse the array and print the data for(int i = 0;i < 20;i++){ System.out.print(values[i] + "/t"); if(( i + 1 ) % 10 == 0){ System.out.println("/n"); } } }} This method is also relatively efficient. If 10,000 data is generated, the time it takes is 0.054s.
Based on the implementation of coordinates in an array, more related solutions can be transformed, and you can refer to relevant information in detail.
The above is about implementing the function of random, non-repetitive numbers in JAVA. Of course, the methods are not limited to these types, but there are other implementation methods. I hope it will be helpful to friends who have been in contact for a while, and I hope it can play a role in attracting and attracting jade.
Original website: http://www.cnblogs.com/hanyonglu/archive/2012/10/18/2730007.html
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.