Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
Solution
C# Solution
Solution1 – Array.Sort + for loop
public class Solution {
public int MissingNumber(int[] nums) {
int n = nums.Length;
Array.Sort(nums);
if(nums[0]>0)
{
return 0;
}
for(int i =1; i<n;i++)
{
if(nums[i]-nums[i-1]>1)
{
return nums[i]-1;
}
}
return n;
}
}
In this solution, we used Array.Sort function to sort the array first.
Then we can use an easy for loop to check if any number is missing.
Time Complexity : O(n log n) + O(n) ≈O(n log n)
Extra Space Complexity : O(1) ➡ used a variable
⭐Solution2
public class Solution {
public int MissingNumber(int[] nums) {
return (1+nums.Length) * nums.Length /2 - nums.Sum();
}
}
How to sum 1 to n, there have a math formula for it
➡ Sum = (1+n)*n/2
And in this problem, we need to start from 0, but that won’t affect our formula.
Time Complexity :O(n)
Extra Space Complexity : O(1)
Java Solution
Solution1
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
if (nums[0] > 0) {
return 0;
}
for (int i = 1; i < n; i++) {
if (nums[i] - nums[i - 1] > 1) {
return nums[i] - 1;
}
}
return n;
}
}
Runtime : 6ms、6ms、6ms ≈ faster than 28% ….
⭐Solution2
class Solution {
public int missingNumber(int[] nums) {
return (nums.length * (nums.length + 1) / 2) - Arrays.stream(nums).sum();
}
}
Runtime : 2ms、2ms、2ms ≈ faster than 30% ….
That means there must be a faster solution, and I should find it someday.
Python3 Solution
Solution1
class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
if nums[0] > 0:
return 0
for i in range(1, n):
if nums[i] - nums[i-1] > 1:
return nums[i] - 1
return n
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
nums.sort((a, b) => a - b);
let n = nums.length;
if (nums[0] > 0) {
return 0;
}
for (let i = 1; i < n; i++) {
if (nums[i] - nums[i-1] > 1) {
return nums[i] - 1;
}
}
return n;
};
⭐Array.sort() method will default to sorting the array elements as strings.
This means that if the elements in the array are numbers, they will be sorted based on their string representations in lexicographical order, rather than their numerical values.
var uagb_data = {"ajax_url":"https:\/\/zyrastory.com\/wp-admin\/admin-ajax.php","uagb_masonry_ajax_nonce":"d9c70811ee"};
var uagb_data = {"ajax_url":"https:\/\/zyrastory.com\/wp-admin\/admin-ajax.php","uagb_masonry_ajax_nonce":"d9c70811ee","uagb_grid_ajax_nonce":"436b663591"};
( function() {
let elements = document.querySelectorAll( '.uagb-post-grid.uagb-block-4c4f60c3 .uagb-post-pagination-wrap a' );
elements.forEach(function(element) {
element.addEventListener("click", function(event){
event.preventDefault();
const link = event.target.getAttribute('href').match( /\/page\/\d+\// )?.[0] || '';
const regex = /\d+/; // regular expression to match a number at the end of the string
const match = link.match( regex ) ? link.match( regex )[0] : 1; // match the regular expression with the link
const pageNumber = parseInt( match ); // extract the number and parse it to an integer
window.UAGBPostGrid._callAjax({"btnBorderStyle":"none","overallBorderColor":"","block_id":"4c4f60c3","categories":"62","displayPostExcerpt":false,"displayPostComment":false,"displayPostImage":false,"imgSize":"medium","linkBox":false,"orderBy":"rand","excludeCurrentPost":true,"postPagination":true,"pageLimit":0,"imageRatio":"2-3","imgEqualHeight":true,"btnBorderLink":true,"btnBorderRadiusLink":true,"overallBorderLink":true,"overallBorderRadiusLink":true,"inheritFromTheme":true,"postType":"post","postDisplaytext":"No post found!","taxonomyType":"category","postsToShow":6,"enableOffset":false,"postsOffset":0,"displayPostDate":true,"excerptLength":15,"displayPostAuthor":false,"displayPostTitle":true,"displayPostTaxonomy":false,"hideTaxonomyIcon":true,"taxStyle":"default","displayPostTaxonomyAboveTitle":"withMeta","imgPosition":"top","bgOverlayColor":"#000000","overlayOpacity":"50","displayPostLink":true,"newTab":false,"ctaText":"Read More","btnHPadding":"","btnVPadding":"","columns":3,"tcolumns":2,"mcolumns":1,"align":"left","width":"wide","order":"desc","rowGap":20,"rowGapTablet":20,"rowGapMobile":20,"columnGap":20,"bgType":"color","bgColor":"#f6f6f6","titleTag":"h4","titleFontSize":"","titleFontSizeType":"px","titleFontFamily":"","titleLineHeightType":"em","titleLoadGoogleFonts":false,"metaColor":"","highlightedTextColor":"#fff","highlightedTextBgColor":"#3182ce","metaFontSize":"","metaFontSizeType":"px","metaFontFamily":"","metaLineHeightType":"em","metaLoadGoogleFonts":false,"excerptColor":"","excerptFontSize":"","excerptFontSizeType":"px","excerptFontFamily":"","excerptLineHeightType":"em","excerptLoadGoogleFonts":false,"displayPostContentRadio":"excerpt","ctaBgType":"color","ctaBgHType":"color","ctaFontSize":"","ctaFontSizeType":"px","ctaFontFamily":"","ctaLineHeightType":"em","ctaLoadGoogleFonts":false,"paddingTop":20,"paddingBottom":20,"paddingRight":20,"paddingLeft":20,"contentPadding":20,"ctaBottomSpace":0,"ctaBottomSpaceTablet":0,"ctaBottomSpaceMobile":0,"imageBottomSpace":15,"titleBottomSpace":15,"metaBottomSpace":15,"excerptBottomSpace":25,"contentPaddingUnit":"px","rowGapUnit":"px","columnGapUnit":"px","excerptBottomSpaceUnit":"px","paginationSpacingUnit":"px","imageBottomSpaceUnit":"px","titleBottomSpaceUnit":"px","metaBottomSpaceUnit":"px","ctaBottomSpaceUnit":"px","paddingBtnUnit":"px","mobilePaddingBtnUnit":"px","tabletPaddingBtnUnit":"px","paddingUnit":"px","mobilePaddingUnit":"px","tabletPaddingUnit":"px","isPreview":false,"taxDivider":", ","titleLetterSpacing":"","titleLetterSpacingType":"px","metaLetterSpacing":"","metaLetterSpacingType":"px","ctaLetterSpacing":"","ctaLetterSpacingType":"px","excerptLetterSpacing":"","excerptLetterSpacingType":"px","useSeparateBoxShadows":true,"boxShadowColor":"#00000070","boxShadowHOffset":0,"boxShadowVOffset":0,"boxShadowBlur":"","boxShadowSpread":"","boxShadowPosition":"outset","boxShadowColorHover":"","boxShadowHOffsetHover":0,"boxShadowVOffsetHover":0,"boxShadowBlurHover":"","boxShadowSpreadHover":"","boxShadowPositionHover":"outset","borderWidth":"","borderStyle":"none","borderColor":"","borderRadius":"","blockName":"post-grid","equalHeight":true,"paginationBgActiveColor":"#e4e4e4","paginationActiveColor":"#333333","paginationBgColor":"#e4e4e4","paginationColor":"#777777","paginationMarkup":"","paginationLayout":"filled","paginationBorderColor":"#888686","paginationBorderSize":1,"paginationSpacing":20,"paginationAlignment":"left","paginationPrevText":"\u00ab Previous","paginationNextText":"Next \u00bb","layoutConfig":[["uagb\/post-image"],["uagb\/post-taxonomy"],["uagb\/post-title"],["uagb\/post-meta"],["uagb\/post-excerpt"],["uagb\/post-button"]],"post_type":"grid","equalHeightInlineButtons":false,"paginationType":"ajax","extended_widget_opts_block":{},"extended_widget_opts":{},"extended_widget_opts_state":"","extended_widget_opts_clientid":"","dateUpdated":""}, pageNumber, '4c4f60c3');
});
});
} )();
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};