Mixing
Compare two array list using O(logn) complexity in java
2
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
We have to array list with same string and same order but in array2 one string is different. I have to find out that string and its position using O(LogN) complexity.
I have solved using O(N) complexity but I want O(LogN) complexity.
My Solution is given below:-
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
for(int i = 1; i <= array2.size(); i++){
if(array1.contains(array2.get(i-1))){
}
else{
System.out.println(array2.get(i-1)+" "+i);
}
}
But its giving O(N) complexity.
java
edited Nov 19 '18 at 13:34
Michael
18.4k73368
asked Nov 19 '18 at 13:31
gaurav
112
|
show 7 more comments
2
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
We have to array list with same string and same order but in array2 one string is different. I have to find out that string and its position using O(LogN) complexity.
I have solved using O(N) complexity but I want O(LogN) complexity.
My Solution is given below:-
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
for(int i = 1; i <= array2.size(); i++){
if(array1.contains(array2.get(i-1))){
}
else{
System.out.println(array2.get(i-1)+" "+i);
}
}
But its giving O(N) complexity.
java
edited Nov 19 '18 at 13:34
Michael
18.4k73368
asked Nov 19 '18 at 13:31
gaurav
112
I don't think its possible with an ArrayList
– Meini
Nov 19 '18 at 13:33
Do you think a logn solution exists?
– user7
Nov 19 '18 at 13:35
1
Not possible. You need to check all the elements. The complexity of what you've given is O(n*m) becauseArrayList.containsmust do a linear search. You can improve to O(n) if one or both collections is aSet, or O(n * log m) if one of the collections is sorted (with a binary search)
– Michael
Nov 19 '18 at 13:36
2
If "one string is different" is unconstrained, this task is impossible and you need to check all elements. If the lists are specified to be exactly equal and the "change" is specified to always be "there's an extra element" or "there's a missing element" or something similarly specific, you could use a binary search to find the first index of a difference.
– Petr Janeček
Nov 19 '18 at 13:38
1
I think Petr's comment is the key here. If the only allowed change is to have one extra element (or one missing element), then it can be done in O(log N) and, @user7, no it doesn't need to be sorted.
– DodgyCodeException
Nov 19 '18 at 13:48
|
show 7 more comments
2
2
2
0
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
We have to array list with same string and same order but in array2 one string is different. I have to find out that string and its position using O(LogN) complexity.
I have solved using O(N) complexity but I want O(LogN) complexity.
My Solution is given below:-
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
for(int i = 1; i <= array2.size(); i++){
if(array1.contains(array2.get(i-1))){
}
else{
System.out.println(array2.get(i-1)+" "+i);
}
}
But its giving O(N) complexity.
java
edited Nov 19 '18 at 13:34
Michael
18.4k73368
asked Nov 19 '18 at 13:31
gaurav
112
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
We have to array list with same string and same order but in array2 one string is different. I have to find out that string and its position using O(LogN) complexity.
I have solved using O(N) complexity but I want O(LogN) complexity.
My Solution is given below:-
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
for(int i = 1; i <= array2.size(); i++){
if(array1.contains(array2.get(i-1))){
}
else{
System.out.println(array2.get(i-1)+" "+i);
}
}
But its giving O(N) complexity.
java
java
edited Nov 19 '18 at 13:34
Michael
18.4k73368
asked Nov 19 '18 at 13:31
gaurav
112
edited Nov 19 '18 at 13:34
Michael
18.4k73368
asked Nov 19 '18 at 13:31
gaurav
112
edited Nov 19 '18 at 13:34
Michael
18.4k73368
edited Nov 19 '18 at 13:34
Michael
18.4k73368
edited Nov 19 '18 at 13:34
Michael
18.4k73368
18.4k73368
asked Nov 19 '18 at 13:31
gaurav
112
asked Nov 19 '18 at 13:31
gaurav
112
asked Nov 19 '18 at 13:31
gaurav
112
112
I don't think its possible with an ArrayList
– Meini
Nov 19 '18 at 13:33
Do you think a logn solution exists?
– user7
Nov 19 '18 at 13:35
1
Not possible. You need to check all the elements. The complexity of what you've given is O(n*m) becauseArrayList.containsmust do a linear search. You can improve to O(n) if one or both collections is aSet, or O(n * log m) if one of the collections is sorted (with a binary search)
– Michael
Nov 19 '18 at 13:36
2
If "one string is different" is unconstrained, this task is impossible and you need to check all elements. If the lists are specified to be exactly equal and the "change" is specified to always be "there's an extra element" or "there's a missing element" or something similarly specific, you could use a binary search to find the first index of a difference.
– Petr Janeček
Nov 19 '18 at 13:38
1
I think Petr's comment is the key here. If the only allowed change is to have one extra element (or one missing element), then it can be done in O(log N) and, @user7, no it doesn't need to be sorted.
– DodgyCodeException
Nov 19 '18 at 13:48
|
show 7 more comments
I don't think its possible with an ArrayList
– Meini
Nov 19 '18 at 13:33
Do you think a logn solution exists?
– user7
Nov 19 '18 at 13:35
1
Not possible. You need to check all the elements. The complexity of what you've given is O(n*m) becauseArrayList.containsmust do a linear search. You can improve to O(n) if one or both collections is aSet, or O(n * log m) if one of the collections is sorted (with a binary search)
– Michael
Nov 19 '18 at 13:36
2
If "one string is different" is unconstrained, this task is impossible and you need to check all elements. If the lists are specified to be exactly equal and the "change" is specified to always be "there's an extra element" or "there's a missing element" or something similarly specific, you could use a binary search to find the first index of a difference.
– Petr Janeček
Nov 19 '18 at 13:38
1
I think Petr's comment is the key here. If the only allowed change is to have one extra element (or one missing element), then it can be done in O(log N) and, @user7, no it doesn't need to be sorted.
– DodgyCodeException
Nov 19 '18 at 13:48
I don't think its possible with an ArrayList
– Meini
Nov 19 '18 at 13:33
I don't think its possible with an ArrayList
– Meini
Nov 19 '18 at 13:33
Do you think a logn solution exists?
– user7
Nov 19 '18 at 13:35
Do you think a logn solution exists?
– user7
Nov 19 '18 at 13:35
1
1
Not possible. You need to check all the elements. The complexity of what you've given is O(n*m) because
ArrayList.contains must do a linear search. You can improve to O(n) if one or both collections is a Set, or O(n * log m) if one of the collections is sorted (with a binary search)– Michael
Nov 19 '18 at 13:36
Not possible. You need to check all the elements. The complexity of what you've given is O(n*m) because
ArrayList.contains must do a linear search. You can improve to O(n) if one or both collections is a Set, or O(n * log m) if one of the collections is sorted (with a binary search)– Michael
Nov 19 '18 at 13:36
2
2
If "one string is different" is unconstrained, this task is impossible and you need to check all elements. If the lists are specified to be exactly equal and the "change" is specified to always be "there's an extra element" or "there's a missing element" or something similarly specific, you could use a binary search to find the first index of a difference.
– Petr Janeček
Nov 19 '18 at 13:38
If "one string is different" is unconstrained, this task is impossible and you need to check all elements. If the lists are specified to be exactly equal and the "change" is specified to always be "there's an extra element" or "there's a missing element" or something similarly specific, you could use a binary search to find the first index of a difference.
– Petr Janeček
Nov 19 '18 at 13:38
1
1
I think Petr's comment is the key here. If the only allowed change is to have one extra element (or one missing element), then it can be done in O(log N) and, @user7, no it doesn't need to be sorted.
– DodgyCodeException
Nov 19 '18 at 13:48
I think Petr's comment is the key here. If the only allowed change is to have one extra element (or one missing element), then it can be done in O(log N) and, @user7, no it doesn't need to be sorted.
– DodgyCodeException
Nov 19 '18 at 13:48
|
show 7 more comments
2 Answers
2
active
oldest
votes
2
Here's a solution that works with lists of any class (as long as its equals method does the right thing).
package so53375733;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String args) {
List<String> list1 = Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh");
List<String> list2 = Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh");
int addedElementIndex = findAddedElement(list1, list2);
System.out.printf(
"Found difference at index %1$d:%n" +
"list1[%1$d] = "%2$s"%n" +
"list2[%1$d] = "%3$s"%n",
addedElementIndex,
addedElementIndex < list1.size() ? list1.get(addedElementIndex) : "[end of list]",
addedElementIndex < list2.size() ? list2.get(addedElementIndex) : "[end of list]");
}
/**
* Performs a binary search for an added (or removed) element of list1 with respect to list2
* (or vice versa). The lists passed as argument should differ only by the addition of one element,
* so that their sizes differ by 1 and the lists are identical except for the extra element in one
* of the lists. If the lists are random-access (i.e. directly indexable in O(1) time) then this
* method's time complexity is O(log N).
* @param list1 A random-access list
* @param list2 A random-access list
* @return The index of the extra element
*/
private static <T> int findAddedElement(List<T> list1, List<T> list2) {
int low = 0;
int high = Math.min(list1.size(), list2.size()) - 1;
if (list1.get(high).equals(list2.get(high)))
return high + 1;
// Loop invariants:
// 1. Elements of list1 are equal to those of list2 at all indices less than 'low'.
// 2. Elements of list1 are NOT equal to those of list2 at all indices >= 'high'.
while (low < high) {
int mid = (low + high) >>> 1; // (low+high)/2 might overflow
if (list1.get(mid).equals(list2.get(mid)))
low = mid + 1;
else
high = mid;
}
return low;
}
}
Output:
Found difference at index 4:
list1[4] = "machintosh"
list2[4] = "quark"
answered Nov 19 '18 at 14:28
DodgyCodeException
3,304424
Got the idea.. +1
– user7
Nov 19 '18 at 14:37
1
Yup, that's what I had in mind, nicely done. For full correctness it's worth saying that(low + high) / 2can overflow, so(low + high) >>> 1with a comment is preferred.
– Petr Janeček
Nov 19 '18 at 14:41
@user7 thanks for the helpful comment. I'll modify my answer.
– DodgyCodeException
Nov 19 '18 at 15:04
1
I think the secondifis still needed to handle the case where the inserted element is at the end.
– user7
Nov 19 '18 at 15:05
add a comment |
1
You could binary search, like this:
public static <T extends Comparable<T>> int findIndexOfNewElement(List<T> list, List<T> modelList) {
int lower = 0;
int upper = list.size() - 1;
int mid = (upper + lower) / 2;
while (lower < upper) {
if (mid >= modelList.size()) {
// The last element is the new one
return modelList.size();
}
if (list.get(mid).compareTo(modelList.get(mid)) != 0) {
// if they are not the same element
// then there has been an insert before or at this index
upper = mid;
} else {
lower = mid + 1;
}
mid = (upper + lower) / 2;
}
return mid;
}
public static void main(String args) {
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
int i = findIndexOfNewElement(array2, array1);
System.out.println(i + " = " + array2.get(i)); // 4 = quark
}
answered Nov 19 '18 at 14:23
xtratic
2,4001822
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53375733%2fcompare-two-array-list-using-ologn-complexity-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
2
Here's a solution that works with lists of any class (as long as its equals method does the right thing).
package so53375733;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String args) {
List<String> list1 = Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh");
List<String> list2 = Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh");
int addedElementIndex = findAddedElement(list1, list2);
System.out.printf(
"Found difference at index %1$d:%n" +
"list1[%1$d] = "%2$s"%n" +
"list2[%1$d] = "%3$s"%n",
addedElementIndex,
addedElementIndex < list1.size() ? list1.get(addedElementIndex) : "[end of list]",
addedElementIndex < list2.size() ? list2.get(addedElementIndex) : "[end of list]");
}
/**
* Performs a binary search for an added (or removed) element of list1 with respect to list2
* (or vice versa). The lists passed as argument should differ only by the addition of one element,
* so that their sizes differ by 1 and the lists are identical except for the extra element in one
* of the lists. If the lists are random-access (i.e. directly indexable in O(1) time) then this
* method's time complexity is O(log N).
* @param list1 A random-access list
* @param list2 A random-access list
* @return The index of the extra element
*/
private static <T> int findAddedElement(List<T> list1, List<T> list2) {
int low = 0;
int high = Math.min(list1.size(), list2.size()) - 1;
if (list1.get(high).equals(list2.get(high)))
return high + 1;
// Loop invariants:
// 1. Elements of list1 are equal to those of list2 at all indices less than 'low'.
// 2. Elements of list1 are NOT equal to those of list2 at all indices >= 'high'.
while (low < high) {
int mid = (low + high) >>> 1; // (low+high)/2 might overflow
if (list1.get(mid).equals(list2.get(mid)))
low = mid + 1;
else
high = mid;
}
return low;
}
}
Output:
Found difference at index 4:
list1[4] = "machintosh"
list2[4] = "quark"
answered Nov 19 '18 at 14:28
DodgyCodeException
3,304424
Got the idea.. +1
– user7
Nov 19 '18 at 14:37
1
Yup, that's what I had in mind, nicely done. For full correctness it's worth saying that(low + high) / 2can overflow, so(low + high) >>> 1with a comment is preferred.
– Petr Janeček
Nov 19 '18 at 14:41
@user7 thanks for the helpful comment. I'll modify my answer.
– DodgyCodeException
Nov 19 '18 at 15:04
1
I think the secondifis still needed to handle the case where the inserted element is at the end.
– user7
Nov 19 '18 at 15:05
add a comment |
2
Here's a solution that works with lists of any class (as long as its equals method does the right thing).
package so53375733;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String args) {
List<String> list1 = Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh");
List<String> list2 = Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh");
int addedElementIndex = findAddedElement(list1, list2);
System.out.printf(
"Found difference at index %1$d:%n" +
"list1[%1$d] = "%2$s"%n" +
"list2[%1$d] = "%3$s"%n",
addedElementIndex,
addedElementIndex < list1.size() ? list1.get(addedElementIndex) : "[end of list]",
addedElementIndex < list2.size() ? list2.get(addedElementIndex) : "[end of list]");
}
/**
* Performs a binary search for an added (or removed) element of list1 with respect to list2
* (or vice versa). The lists passed as argument should differ only by the addition of one element,
* so that their sizes differ by 1 and the lists are identical except for the extra element in one
* of the lists. If the lists are random-access (i.e. directly indexable in O(1) time) then this
* method's time complexity is O(log N).
* @param list1 A random-access list
* @param list2 A random-access list
* @return The index of the extra element
*/
private static <T> int findAddedElement(List<T> list1, List<T> list2) {
int low = 0;
int high = Math.min(list1.size(), list2.size()) - 1;
if (list1.get(high).equals(list2.get(high)))
return high + 1;
// Loop invariants:
// 1. Elements of list1 are equal to those of list2 at all indices less than 'low'.
// 2. Elements of list1 are NOT equal to those of list2 at all indices >= 'high'.
while (low < high) {
int mid = (low + high) >>> 1; // (low+high)/2 might overflow
if (list1.get(mid).equals(list2.get(mid)))
low = mid + 1;
else
high = mid;
}
return low;
}
}
Output:
Found difference at index 4:
list1[4] = "machintosh"
list2[4] = "quark"
answered Nov 19 '18 at 14:28
DodgyCodeException
3,304424
Got the idea.. +1
– user7
Nov 19 '18 at 14:37
1
Yup, that's what I had in mind, nicely done. For full correctness it's worth saying that(low + high) / 2can overflow, so(low + high) >>> 1with a comment is preferred.
– Petr Janeček
Nov 19 '18 at 14:41
@user7 thanks for the helpful comment. I'll modify my answer.
– DodgyCodeException
Nov 19 '18 at 15:04
1
I think the secondifis still needed to handle the case where the inserted element is at the end.
– user7
Nov 19 '18 at 15:05
add a comment |
2
2
2
Here's a solution that works with lists of any class (as long as its equals method does the right thing).
package so53375733;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String args) {
List<String> list1 = Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh");
List<String> list2 = Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh");
int addedElementIndex = findAddedElement(list1, list2);
System.out.printf(
"Found difference at index %1$d:%n" +
"list1[%1$d] = "%2$s"%n" +
"list2[%1$d] = "%3$s"%n",
addedElementIndex,
addedElementIndex < list1.size() ? list1.get(addedElementIndex) : "[end of list]",
addedElementIndex < list2.size() ? list2.get(addedElementIndex) : "[end of list]");
}
/**
* Performs a binary search for an added (or removed) element of list1 with respect to list2
* (or vice versa). The lists passed as argument should differ only by the addition of one element,
* so that their sizes differ by 1 and the lists are identical except for the extra element in one
* of the lists. If the lists are random-access (i.e. directly indexable in O(1) time) then this
* method's time complexity is O(log N).
* @param list1 A random-access list
* @param list2 A random-access list
* @return The index of the extra element
*/
private static <T> int findAddedElement(List<T> list1, List<T> list2) {
int low = 0;
int high = Math.min(list1.size(), list2.size()) - 1;
if (list1.get(high).equals(list2.get(high)))
return high + 1;
// Loop invariants:
// 1. Elements of list1 are equal to those of list2 at all indices less than 'low'.
// 2. Elements of list1 are NOT equal to those of list2 at all indices >= 'high'.
while (low < high) {
int mid = (low + high) >>> 1; // (low+high)/2 might overflow
if (list1.get(mid).equals(list2.get(mid)))
low = mid + 1;
else
high = mid;
}
return low;
}
}
Output:
Found difference at index 4:
list1[4] = "machintosh"
list2[4] = "quark"
answered Nov 19 '18 at 14:28
DodgyCodeException
3,304424
Here's a solution that works with lists of any class (as long as its equals method does the right thing).
package so53375733;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String args) {
List<String> list1 = Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh");
List<String> list2 = Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh");
int addedElementIndex = findAddedElement(list1, list2);
System.out.printf(
"Found difference at index %1$d:%n" +
"list1[%1$d] = "%2$s"%n" +
"list2[%1$d] = "%3$s"%n",
addedElementIndex,
addedElementIndex < list1.size() ? list1.get(addedElementIndex) : "[end of list]",
addedElementIndex < list2.size() ? list2.get(addedElementIndex) : "[end of list]");
}
/**
* Performs a binary search for an added (or removed) element of list1 with respect to list2
* (or vice versa). The lists passed as argument should differ only by the addition of one element,
* so that their sizes differ by 1 and the lists are identical except for the extra element in one
* of the lists. If the lists are random-access (i.e. directly indexable in O(1) time) then this
* method's time complexity is O(log N).
* @param list1 A random-access list
* @param list2 A random-access list
* @return The index of the extra element
*/
private static <T> int findAddedElement(List<T> list1, List<T> list2) {
int low = 0;
int high = Math.min(list1.size(), list2.size()) - 1;
if (list1.get(high).equals(list2.get(high)))
return high + 1;
// Loop invariants:
// 1. Elements of list1 are equal to those of list2 at all indices less than 'low'.
// 2. Elements of list1 are NOT equal to those of list2 at all indices >= 'high'.
while (low < high) {
int mid = (low + high) >>> 1; // (low+high)/2 might overflow
if (list1.get(mid).equals(list2.get(mid)))
low = mid + 1;
else
high = mid;
}
return low;
}
}
Output:
Found difference at index 4:
list1[4] = "machintosh"
list2[4] = "quark"
answered Nov 19 '18 at 14:28
DodgyCodeException
3,304424
edited Nov 19 '18 at 15:17
answered Nov 19 '18 at 14:28
DodgyCodeException
3,304424
answered Nov 19 '18 at 14:28
DodgyCodeException
3,304424
answered Nov 19 '18 at 14:28
DodgyCodeException
3,304424
3,304424
Got the idea.. +1
– user7
Nov 19 '18 at 14:37
1
Yup, that's what I had in mind, nicely done. For full correctness it's worth saying that(low + high) / 2can overflow, so(low + high) >>> 1with a comment is preferred.
– Petr Janeček
Nov 19 '18 at 14:41
@user7 thanks for the helpful comment. I'll modify my answer.
– DodgyCodeException
Nov 19 '18 at 15:04
1
I think the secondifis still needed to handle the case where the inserted element is at the end.
– user7
Nov 19 '18 at 15:05
add a comment |
Got the idea.. +1
– user7
Nov 19 '18 at 14:37
1
Yup, that's what I had in mind, nicely done. For full correctness it's worth saying that(low + high) / 2can overflow, so(low + high) >>> 1with a comment is preferred.
– Petr Janeček
Nov 19 '18 at 14:41
@user7 thanks for the helpful comment. I'll modify my answer.
– DodgyCodeException
Nov 19 '18 at 15:04
1
I think the secondifis still needed to handle the case where the inserted element is at the end.
– user7
Nov 19 '18 at 15:05
Got the idea.. +1
– user7
Nov 19 '18 at 14:37
Got the idea.. +1
– user7
Nov 19 '18 at 14:37
1
1
Yup, that's what I had in mind, nicely done. For full correctness it's worth saying that
(low + high) / 2 can overflow, so (low + high) >>> 1 with a comment is preferred.– Petr Janeček
Nov 19 '18 at 14:41
Yup, that's what I had in mind, nicely done. For full correctness it's worth saying that
(low + high) / 2 can overflow, so (low + high) >>> 1 with a comment is preferred.– Petr Janeček
Nov 19 '18 at 14:41
@user7 thanks for the helpful comment. I'll modify my answer.
– DodgyCodeException
Nov 19 '18 at 15:04
@user7 thanks for the helpful comment. I'll modify my answer.
– DodgyCodeException
Nov 19 '18 at 15:04
1
1
I think the second
if is still needed to handle the case where the inserted element is at the end.– user7
Nov 19 '18 at 15:05
I think the second
if is still needed to handle the case where the inserted element is at the end.– user7
Nov 19 '18 at 15:05
add a comment |
1
You could binary search, like this:
public static <T extends Comparable<T>> int findIndexOfNewElement(List<T> list, List<T> modelList) {
int lower = 0;
int upper = list.size() - 1;
int mid = (upper + lower) / 2;
while (lower < upper) {
if (mid >= modelList.size()) {
// The last element is the new one
return modelList.size();
}
if (list.get(mid).compareTo(modelList.get(mid)) != 0) {
// if they are not the same element
// then there has been an insert before or at this index
upper = mid;
} else {
lower = mid + 1;
}
mid = (upper + lower) / 2;
}
return mid;
}
public static void main(String args) {
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
int i = findIndexOfNewElement(array2, array1);
System.out.println(i + " = " + array2.get(i)); // 4 = quark
}
answered Nov 19 '18 at 14:23
xtratic
2,4001822
add a comment |
1
You could binary search, like this:
public static <T extends Comparable<T>> int findIndexOfNewElement(List<T> list, List<T> modelList) {
int lower = 0;
int upper = list.size() - 1;
int mid = (upper + lower) / 2;
while (lower < upper) {
if (mid >= modelList.size()) {
// The last element is the new one
return modelList.size();
}
if (list.get(mid).compareTo(modelList.get(mid)) != 0) {
// if they are not the same element
// then there has been an insert before or at this index
upper = mid;
} else {
lower = mid + 1;
}
mid = (upper + lower) / 2;
}
return mid;
}
public static void main(String args) {
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
int i = findIndexOfNewElement(array2, array1);
System.out.println(i + " = " + array2.get(i)); // 4 = quark
}
answered Nov 19 '18 at 14:23
xtratic
2,4001822
add a comment |
1
1
1
You could binary search, like this:
public static <T extends Comparable<T>> int findIndexOfNewElement(List<T> list, List<T> modelList) {
int lower = 0;
int upper = list.size() - 1;
int mid = (upper + lower) / 2;
while (lower < upper) {
if (mid >= modelList.size()) {
// The last element is the new one
return modelList.size();
}
if (list.get(mid).compareTo(modelList.get(mid)) != 0) {
// if they are not the same element
// then there has been an insert before or at this index
upper = mid;
} else {
lower = mid + 1;
}
mid = (upper + lower) / 2;
}
return mid;
}
public static void main(String args) {
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
int i = findIndexOfNewElement(array2, array1);
System.out.println(i + " = " + array2.get(i)); // 4 = quark
}
answered Nov 19 '18 at 14:23
xtratic
2,4001822
You could binary search, like this:
public static <T extends Comparable<T>> int findIndexOfNewElement(List<T> list, List<T> modelList) {
int lower = 0;
int upper = list.size() - 1;
int mid = (upper + lower) / 2;
while (lower < upper) {
if (mid >= modelList.size()) {
// The last element is the new one
return modelList.size();
}
if (list.get(mid).compareTo(modelList.get(mid)) != 0) {
// if they are not the same element
// then there has been an insert before or at this index
upper = mid;
} else {
lower = mid + 1;
}
mid = (upper + lower) / 2;
}
return mid;
}
public static void main(String args) {
ArrayList<String> array1 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "machintosh"));
ArrayList<String> array2 = new ArrayList<>(Arrays.asList("netflix", "dhoni", "harini", "obama", "quark", "machintosh"));
int i = findIndexOfNewElement(array2, array1);
System.out.println(i + " = " + array2.get(i)); // 4 = quark
}
answered Nov 19 '18 at 14:23
xtratic
2,4001822
answered Nov 19 '18 at 14:23
xtratic
2,4001822
answered Nov 19 '18 at 14:23
xtratic
2,4001822
answered Nov 19 '18 at 14:23
xtratic
2,4001822
2,4001822
add a comment |
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53375733%2fcompare-two-array-list-using-ologn-complexity-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I don't think its possible with an ArrayList
– Meini
Nov 19 '18 at 13:33
Do you think a logn solution exists?
– user7
Nov 19 '18 at 13:35
1
Not possible. You need to check all the elements. The complexity of what you've given is O(n*m) because
ArrayList.containsmust do a linear search. You can improve to O(n) if one or both collections is aSet, or O(n * log m) if one of the collections is sorted (with a binary search)– Michael
Nov 19 '18 at 13:36
2
If "one string is different" is unconstrained, this task is impossible and you need to check all elements. If the lists are specified to be exactly equal and the "change" is specified to always be "there's an extra element" or "there's a missing element" or something similarly specific, you could use a binary search to find the first index of a difference.
– Petr Janeček
Nov 19 '18 at 13:38
1
I think Petr's comment is the key here. If the only allowed change is to have one extra element (or one missing element), then it can be done in O(log N) and, @user7, no it doesn't need to be sorted.
– DodgyCodeException
Nov 19 '18 at 13:48