I am quite new to LinkedLists and was scratching my head as to how to tackle this problem:
"Write a piece of code that counts the number of duplicate elements in a linked list. That is, the number of elements whose values are repeated at an earlier index in the list. Assume that all duplicates in the list occur consecutively. For example, the list [1, 1, 3, 5, 5, 5, 5, 7, 7, 11] contains five duplicates: one duplicate of element value 1, three duplicates of element value 5, and one duplicate of element value 7."
Eventually, I came up with this answer:
//Initialization of variables and example elements
LinkedList<Integer> linkL = new LinkedList<Integer>();
int count = 0;
int currNum;
int compare;
linkL.add(11);
linkL.add(7);
linkL.add(7);
linkL.add(5);
linkL.add(5);
linkL.add(5);
linkL.add(5);
linkL.add(3);
linkL.add(1);
linkL.add(1);
Iterator<Integer> itr = linkL.iterator();
//Initalizes first two to compare.
currNum = itr.next();
System.out.println("curr num = " currNum);
compare = itr.next();
System.out.println("curr num = " compare);
//compares all elements in the list
while (itr.hasNext())
{
//if current element == next, advances the dupe count
if(currNum == compare)
{
howManyDupe ;
//advances the current element and fetches the next one
currNum = compare;
compare = itr.next();
}else //if not goes to the next set of elements
{
currNum = compare;
compare = itr.next();
}
}
//Gets the slopover
if(currNum == compare)
{
howManyDupe ;
System.out.println(howManyDupe "duplicates in this list ");
}else
{
System.out.println(howManyDupe " dupliates in this list ");
}
This code here works as described in the problem, but I wondered if anyone had any ideas of if there was a "better" way of doing it. Such as not using so many if statements, a better way to catch the slopover, a way of not having to initialize the first two elements, a way of writing it in fewer lines, etc. Please note: we were required to use the LinkedList class and not to create our own nodes and LinkedLists.
CodePudding user response：
public static int countDuplicates(List<?> list) {
Object previous = null;
int counter = 0;
for(Object element: list) {
if(previous != null && previous.equals(element))
counter ;
else
previous = element;
}
return counter;
}
CodePudding user response：
Here is a "cleaned up" version with comments to walk you through.
public int countDuplicates(LinkedList<Integer> linkL) {
/*
* First, I liked how you got the first two values
* before beginning the loop, but that would fail
* if there are fewer than two elements.
*
* Obviously a list of size 0 or 1 can have no
* duplicates, so let's test that condition first
* and return immediately.
*/
if (linkL.size() < 2) return 0;
/*
* Now we can define our variables and retrieve
* the first two values
*/
int howManyDupe = 0;
Iterator<Integer> itr = linkL.iterator();
int currNum = itr.next();
int compare = itr.next();
/*
* Doing the first comparison _before_ the loop
* eliminates the "slopover" scenario
*/
if (currNum == compare) {
howManyDupe ;
}
/*
* Now we loop.
*
* In your example, you had an if/else where the
* two blocks were mostly identical.
*
* Instead, we can move those statements outside
* of the if, leaving a much simpler block.
*
* Also currNum & compare will have "old" values
* at the beginning of the loop, because they
* were set before the loop, or in the last
* iteration, so we update them first
*/
while (itr.hasNext()) {
currNum = compare;
compare = itr.next();
if (currNum == compare) {
howManyDupe ;
}
}
return howManyDupe;
}
CodePudding user response：
In the problem statement, it's worth noting that the question doesn't require you to count CONSECUTIVE duplicates, just that you are allowed to assume that the list is already sorted numerically.
So.. if the question is to count duplicates, and optionally output how many duplicates of each number are present, but not necessarily CONSECUTIVE duplicates, then this code will work.
EDIT: I've added a piece at the bottom for total duplicates only.
EDIT: Bah. I didn't read your comment at the bottom, saying you weren't allowed to create your own nodes. These solutions won't work for you, then... but I'll leave them posted here for your learning enjoyment.
// load all values into a map, and increment their count as you go:
Map<Integer, Integer> valueMap = new HashMap<>();
for (Integer int : linkedList) {
if (valueMap.containsKey(int)) {
int count = valueMap.get(int);
valueMap.put(int, count 1);
} else {
valueMap.put(int, 1);
}
// read through the map for duplicates and output the results:
for (Map.Entry<String, String> entry : entrySet) {
if (entry.getValue() > 1) {
System.out.println("Number: " entry.getKey()
" has: " (entry.getValue() -1) " duplicates);
}
Another clever way if the range of values are known and not too large, is just to use an array's index position:
Integer biggestValueInList = Collections.max(linkedList);
int [] array = new int[biggestValueInList];
for (Integer int : linkedList) {
array[int] = array[int] 1;
}
for (int i = 0; i < array.length; i ) {
if (array[i] > 1) {
System.out.println("Number: " i " has: " (array[i] - 1) " duplicates");
}
}
Note that both of these methods require you to loop through the list twice, so it's possibly not as execution-efficient, but it's less lines of code... and both methods will work even if the duplicates aren't sequential/consecutive.
Each of these solutions can easily be modified to count the total number of duplicates, simply by changing the 2nd FOR loop in each solution:
int totalDuplicates = 0;
for (int i = 0; i < array.length; i ) {
if (array[i] > 1) {
totalDuplicates = totalDuplicates (array[i] - 1);
}
}
System.out.println("Total duplicates = " totalDuplicates);