First we can use Brute Force to into a two-step` algorithm:
find all the \((\) and \()\) and get their indices;
determine the indices that need to be deleted;
creates a new string from the index of the deleted characters.
We can use a Stack to record the indices of all \((\) and \()\) s. When scanning to the end of the string, all indices remaining in the Stack are \((\) and \()\) s that do not match.
We also need to use a \(\texttt{Set}\) to keep track of unmatched \((\) and \()\) s. Then Delete each character that needs to be deleted according to the indices, and return the recreated string.
We can just simulate the process from the begin to end.
First we split the given string \(\textit{path}\) into a list of strings by the slash \(/\), denoted as names. According to the canonical path in the problem description, the strings contained in names can only be the following:
empty string;
a dot .;
two dots ..;
a directory name containing only English letters, numbers, or _.
If we meet empty string or ., we can ignore them because empty string means nothing, and . means the current directory itself, so we don’t need to change directories.
If we meet .. or “directory names”, we can use a Stack to maintain each directory name in the path. When we encounter “two dots”, we need to change the directory to the parent directory. As the stack is not empty, we pop the directory of the stack. When we encounter a “directory”, we put it to the stack.
Finally we need to iterate each string in names and do the above. After all operations are completed, we connect the strings from the bottom of the stack to the top of the stack with /, and then add / at the top to indicate the root directory, and we can get the simplified Canonical path.
Here are 9 approaches to solve this problem in Java, which is Brute Force, Count, Hash, In-place Marked, Sorting, Index Sort, Binary Search, Bit Manipulation, Fast Slow Pointers.
Since solve the problem without modifying the array nums and uses only constant extra space, we can use Brute Force to solve it.
It’s easy to use 2 loops to do it, but the time complexity is \(O(n^2)\), so it wouldn’t accepted as timeout.
1 2 3 4 5 6 7 8 9 10 11 12 13
// 2 Loops publicstaticintfindDuplicate_2loops(int[] nums) { intlen= nums.length; for (inti=0; i < len; i++) { for (intj= i + 1; j < len; j++) { if (nums[i] == nums[j]) { return nums[i]; } } }
return len; }
Analysis
Time Complexity: \(O(n^2)\)
Space Complexity: \(O(1)\)
Count
Count the frequency of the num in the array.
With extra \(O(n)\) space, without modifying the input.
1 2 3 4 5 6 7 8 9 10 11 12
publicstaticintfindDuplicate(int[] nums) { intlen= nums.length; int[] cnt = newint[len + 1]; for (inti=0; i < len; i++) { cnt[nums[i]]++; if (cnt[nums[i]] > 1) { return nums[i]; } }
return len; }
Analysis
Time Complexity: \(O(n)\)
Space Complexity: \(O(n)\)
Hash
Using a \(\texttt{HashSet}\) to record the occurrence of each number.
With extra \(O(n)\) space, without modifying the input.
1 2 3 4 5 6 7 8 9 10 11
publicstaticintfindDuplicate_set(int[] nums) { Set<Integer> set = newHashSet<>(); intlen= nums.length; for (inti=0; i < len; i++) { if (!set.add(nums[i])) { return nums[i]; } }
return len; }
Analysis
Time Complexity: \(O(n)\)
Space Complexity: \(O(n)\)
Marking visited value within the array
Since all values of the array are between \([1 \dots n]\) and the array size is \(n+1\), while scanning the array from left to right, we set the \(\textit{nums}[n]\) to its negative value.
With extra \(O(1)\) space, with modifying the input.
1 2 3 4 5 6 7 8 9 10 11 12 13
// Visited publicstaticintfindDuplicate_mark(int[] nums) { intlen= nums.length; for (int num : nums) { intidx= Math.abs(num); if (nums[idx] < 0) { return idx; } nums[idx] = -nums[idx]; }
return len; }
Analysis
Time Complexity: \(O(n)\)
Space Complexity: \(O(1)\)
Sort
Sorting the array first, then use a loop from \(1\) to \(n\).
With extra \(O(nlogn)\) space, modifying the input.
1 2 3 4 5 6 7 8 9 10 11
publicstaticintfindDuplicate_sort(int[] nums) { Arrays.sort(nums); intlen= nums.length; for (inti=1; i < len; i++) { if (nums[i] == nums[i - 1]) { return nums[i]; } }