CODEWITHSUNDEEP
algorithm
user10565550
user10565550

Reputation:

similar code , same function , can't figure it out any difference btw them

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/discuss/93007/simple-java-in-place-sort-solution

Could you please check above link?

I can't understand the code

while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1])

What is the difference between those two?

1) nums[i] != i+1
2) nums[i] != nums[nums[i]-1]

for example 

index 0 : 1
index 1 : 2
index 2 : 3

Then, the first one just simply using the index we can check index+1 is the value or not.

and Second one, 

nums[0] = nums[nums[i]-1]
nums[0] = nums[nums[0]-1]
nums[0] = nums[1-1]
nums[0] = nums[0]

It is also ultimately the same thing, just to prove that index value = index+1.

But why while loop have to have both condition? or we can just use one of that?

Upvotes: 2

Views: 74

Answers (2)

Jean-Baptiste Yunès
Jean-Baptiste Yunès

Reputation: 36441

  1. nums[i] != i+1

Is the value at its place? If not may be swap it to its place...

This is needed because you have to test every position

  1. nums[i] != nums[nums[i]-1]

Does the value needs to be swapped to its place ?

This is needed because the algorithm place every element in a chain to its place.

Take this example:

[3,1,2,4,6,5,8,7]

it should be clear that you need to rearrange 1,2,3 and 5,6 and 7,8.

Lets look how the sorting takes place:

i:0 [3,1,2,4,6,5,8,7] 3<->2
i:0 [2,1,3,4,6,5,8,7] 2<->1
i:0 [1,2,3,4,6,5,8,7] now 1 is at its place, go to the right and find another chain
i:1 [1,2,3,4,6,5,8,7] 2 at its place
i:2 [1,2,3,4,6,5,8,7] 3 at its place
i:3 [1,2,3,4,6,5,8,7] 4 at its place
i:4 [1,2,3,4,6,5,8,7] 6<->5
i:4 [1,2,3,4,5,6,8,7] now is 5 at its place, go to the right and find another chain
i:5 [1,2,3,4,5,6,8,7] 6 at its place
i:6 [1,2,3,4,5,6,8,7] 8<->7
i:6 [1,2,3,4,5,6,7,8] now is 7 at its place, go to the right and find another chain
i:7 [1,2,3,4,5,6,7,8] 8 at its place
END

Beware that the algorithm can't sort the array given in the link! What the algorithm provides is that if in the initial array element e is present, then it will be at its place at the end. In the given example, 3 is present two times, one is placed at the right place but the other not! But the end of the algorithm retains values that are at their right places and ignores others. Then it's a "sorting and doublons removal" algorithm or "longest strictly increasing sequence algorithm".

Upvotes: 0

Nemo
Nemo

Reputation: 71605

I agree the second condition is unnecessary. In fact, I think it needlessly clutters the code.

In English, the code essentially says "if [something] and (x != y), then swap x and y". All the "x != y" check does is prevent swapping x with (something equal to) itself. But that is a no-op, so that check can be removed without changing the behavior or O(n) performance.

Removing that check makes it easier to read the algorithm: "For each slot i, while the item at slot i is wrong, swap it to where it belongs."

[Update]

Whoops! I just realized the point of the check... It prevents a potential infinite loop where you keep swapping the same value back and forth. (Because the condition is actually a "while", not an "if".)

So the algorithm as presented is correct.

Upvotes: 2

Related Questions