当前位置:网站首页>Single element of an ordered array
Single element of an ordered array
2022-07-01 18:13:00 【Ustinian%】
Single element of an ordered array
Topic link :540. A single element in an ordered array
Title Description :
Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .
Please find and return the number that only appears once .
The solution you design must meet O(log n) Time complexity and O(1) Spatial complexity .
Example 1:
Input : nums = [1,1,2,3,3,4,4,8,8]
Output : 2
Example 2:
Input : nums = [3,3,7,7,10,11,11]
Output : 10
Tips :
1 <= nums.length <= 105
0 <= nums[i] <= 105
Solution 1 :
Because in addition to that single element in the array , Other elements appear in pairs , So we can use XOR , Use a variable to XOR all the numbers in the array once , The final result is the single element .
x^x = 0,x^0 = x;
Time complexity O(N)
Spatial complexity O(1)
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
// Record the final answer
int ans = 0;
for(int i = 0;i<nums.size();i++)
{
ans^=nums[i];
}
return ans;
}
};
Solution 2 :
We can also use the dichotomy method to solve this problem .
We can think about it like this : Before this single element existed , The numbers of arrays are all in pairs , So if you don't consider “ special ” Of a single element , We have a conclusion : The subscript corresponding to the first of the paired elements must be even , The subscript corresponding to the second of the paired elements must be odd .
When we insert this single element into the array , The first half of the single element will still have the above conclusion , However, the latter half of a single element will cause the conclusion to flip due to the insertion of the single element . Thus there are : The subscript corresponding to the first of the paired elements must be odd , The subscript corresponding to the second of the paired elements must be even .
Therefore, the duality of our problem comes out , We can according to the equinox mid To discuss the situation according to the parity of :
- If mid The subscript is even , According to the initial conclusion , Under normal circumstances, the value of the even subscript will be equal to the value of the next number . So if this condition is met , Prove that the single element is not mid Left side , It should be in mid The right side of does not include mid, So we update the interval to [mid+1,right], On the contrary, if the current mid If it is not equal to the value of the next number , Then the value of a single element should be mid The left side of includes mid, Therefore, the update interval is [left,mid]
- If mid Subscripts are odd , According to the initial conclusion , Under normal circumstances, the value of an odd subscript will be equal to the value of its previous number . So if this condition is met , Prove that the single element is not mid Left side , It should be in mid The right side of does not include mid, So we update the interval to [mid+1,right], On the contrary, if the current mid If it is not equal to the value of its previous number , Then the value of a single element should be mid The left side of includes mid, Therefore, the update interval is [left,mid]
Time complexity O(logN)
Spatial complexity O(1)
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n = nums.size();
// It's a special verdict
if(n==1)
{
return nums[0];
}
// Dichotomous thinking
// Before the existence of this single element , The numbers in the array are all in pairs , So the number of pairs The subscript of the first number is even, and the subscript of the second number is odd
// But after inserting this single element into a certain position , The first half of the data of the single element will still keep the subscript of the first number even , The subscript of the second number is odd
// But in the second half of the single element, the nature of the data will change
// The second half of the data will become : The subscript of the first number of paired data is odd , The subscript of the second number is even
int left = 0;
int right = n-1;
while(left<right)
{
int mid = left+(right-left)/2;
// If mid The value of the subscript is even
if((mid&1)==0)
{
// If mid Subscript value and mid+1 The values of subscripts are equal
// The number that proves to occur only once appears in mid The right side of does not include mid
// Therefore, the update interval is [mid+1,right]
if(mid+1<n&&nums[mid]==nums[mid+1])
{
left = mid+1;
}
// Otherwise, the update interval is [left,mid]
else
{
right = mid;
}
}
// If mid The value of the subscript is an odd number
else
{
// If mid Subscript value and mid-1 The value of is equal
// The number that proves to appear only once is mid The right side of does not include mid
// Therefore, the update interval is [mid+1,right]
if(mid-1>=0&&nums[mid-1]==nums[mid])
{
left = mid+1;
}
// Otherwise, the update interval is [left,mid]
else
{
right = mid;
}
}
}
return nums[right];
}
};
边栏推荐
- Flex layout
- . Net cloud native architect training camp (permission system code implements actionaccess) -- learning notes
- Nielseniq found that 60% of the re launched products had poor returns
- Slider verification code identification gadget display
- DNS
- Petrv2: a unified framework for 3D perception of multi camera images
- Pyqt5, draw a histogram on the control
- Easycvr accesses the equipment through the national standard gb28181 protocol. What is the reason for the automatic streaming of the equipment?
- Good looking UI mall source code has been scanned, no back door, no encryption
- transform. Forward and vector3 Differences in the use of forward
猜你喜欢
[PHP foundation] realize the connection between PHP and SQL database
Penetration practice vulnhub range Tornado
Flex layout
An example of data analysis of an old swatch and an old hard disk disassembly and assembly combined with the sensor of an electromagnetic press
[C supplement] [string] display the schedule of a month by date
Explain in detail the process of realizing Chinese text classification by CNN
Definition of rotation axis in mujoco
ISO 27001 Information Security Management System Certification
Distributed task queue: Celery usage record
The new server is packaged with the source code of H5 mall with an operation level value of several thousand
随机推荐
股票万1免5证券开户是合理安全的吗,怎么讲
Flex layout
Definition of rotation axis in mujoco
MFC obtains local IP (used more in network communication)
Radhat builds intranet Yum source server
Setting up a time server requires the client to automatically synchronize the time of the server at 9 a.m. every day
Redis主从实现10秒检查与恢复
Is online stock account opening safe? Is it reliable?
Work and leisure suggestions of old programmers
Intelligent operation and maintenance practice: banking business process and single transaction tracking
Software construction scheme of smart factory collaborative management and control application system
目前炒期货在哪里开户最正规安全?怎么期货开户?
At present, where is the most formal and safe account opening for futures speculation? How to open a futures account?
Is the software of futures pioneer formal and safe? Which futures company is safer to choose?
February 16, 2022 Daily: graph neural network self training method under distribution and migration
Set the style of QT property sheet control
ACM mm 2022 video understanding challenge video classification track champion autox team technology sharing
Cassette helicopter and alternating electric field magnetic manometer DPC
Penetration practice vulnhub range Tornado
How to use JMeter function and mockjs function in metersphere interface test