Python

for i in range(len(list1)): try: j = list2.index(list1[i]) print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']') except ValueError: print("no match for", list1[i])

See more:

Python

l

list1 = [15, 12, 13, 19, 14] list2 = [19, 13, 15, 12, 14] def function(l1, l2): for i in range(len(list1)): for j in range(len(list2)): if list1[i] == list2[j]: print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']') function(list1, list2)

How to make a less time complexity algorithm?

I have tried the above code, but I want another efficient one.

Comments

Try the following which may, or may not be more efficient:

Python

for i in range(len(list1)): try: j = list2.index(list1[i]) print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']') except ValueError: print("no match for", list1[i])

Permalink

Share this answer

Comments

[no name]
3-May-21 10:16am

Thank you so much :)

Richard MacCutchan
3-May-21 10:38am

You are welcome, but see CPallini's comment below.

CPallini
3-May-21 10:23am

Should be still O(N^2),according to:

https://wiki.python.org/moin/TimeComplexity

However, the code is nice. Have my 5.

https://wiki.python.org/moin/TimeComplexity

However, the code is nice. Have my 5.

Richard MacCutchan
3-May-21 10:30am

Thanks. I could not see a Big-O value for the index method, although it does reduce the number of iterations in the second loop. The same could be done by a

`break`

statement in the original.
CPallini
3-May-21 10:33am

Richard MacCutchan
3-May-21 10:38am

:thumbsup:

A little improvement, assuming there is only 1 match.

Only a little better than O(n²)

There is another approach where complexity is the one of sort function (O(n log(n)).

Dichotomic search - Wikipedia[^]

Binary search algorithm - Wikipedia[^]

Python

list1 = [15, 12, 13, 19, 14] list2 = [19, 13, 15, 12, 14] def function(l1, l2): for i in range(len(list1)): for j in range(len(list2)): if list1[i] == list2[j]: print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')break; # gets out of loopfunction(list1, list2)

Only a little better than O(n²)

There is another approach where complexity is the one of sort function (O(n log(n)).

Python

list1 = [15, 12, 13, 19, 14] list2 = [19, 13, 15, 12, 14]# create a list with indices of list2 list3 = [0, 1, 2, 3, 4]# then do an indirect sort # I sort list3 on the values of list2 def sortindirect(elem): return list2[elem] list3.sort(key=sortindirect) # list3 = [4, 1, 3, 0, 2]def function(l1, l2): for i in range(len(list1)):# Then rather that scan list2 for a match, I search list2 using dichotomyif list1[i] == list2[list3[j]]: print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')~~for j in range(len(list2)):~~# drop this loop and replace with a dichotomy search

Dichotomic search - Wikipedia[^]

Binary search algorithm - Wikipedia[^]

Python

# this print list2 as is for i in range(len(list2)): print (list2[i]) # this print list2 sorted for i in range(len(list3)): print (list2[[list3[i]])

Permalink

Share this answer

v3

Comments

CPallini
3-May-21 15:58pm

5.

Patrice T
3-May-21 16:01pm

Thank you

Michel Jakson
3-May-21 16:22pm

Patrice .. Can you explain your code please I do not get it? 'O(nlog(n))'

Patrice T
3-May-21 16:51pm

This is complexity of 'sort'

Michel Jakson
3-May-21 16:52pm

Yes I know, I mean your second code, I do not get it.

Patrice T
3-May-21 17:06pm

Done a correction in my code.

Michel Jakson
3-May-21 17:15pm

This is the whole code right?

list1 = [15, 12, 13, 19, 14]

list2 = [19, 13, 15, 12, 14]

list3 = [0, 1, 2, 3, 4]

def sortindirect(elem):

return list2[elem]

list3.sort(key=sortindirect)

for i in range(len(list1)):

for j in range(len(list2)):

if list1[i] == list2[list3[j]]:

print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')

list1 = [15, 12, 13, 19, 14]

list2 = [19, 13, 15, 12, 14]

list3 = [0, 1, 2, 3, 4]

def sortindirect(elem):

return list2[elem]

list3.sort(key=sortindirect)

for i in range(len(list1)):

for j in range(len(list2)):

if list1[i] == list2[list3[j]]:

print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')

Patrice T
3-May-21 17:25pm

mostly

Patrice T
3-May-21 17:39pm

Updated solution.

Binary search is left to you.

Binary search is left to you.

Michel Jakson
3-May-21 17:17pm

I'm sorry if i'm asking too much, i'm new in python, so i'm trying to develop it. Thanks a lot.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

Actually it finds the matching values.

If you do not know python or java, it does not matter, I just want to know the efficient algorithm to solve this problem. this one takes O(n^2).

If you do not know python or java, it does not matter, I just want to know the efficient algorithm to solve this problem. this one takes O(n^2).

If you do not know python or java, it does not matter, I just want to know the efficient algorithm to solve this problem. this one takes O(n^2).