精华内容
下载资源
问答
  • 2021-03-14 23:11:49

    题目描述

    已知一维数组中的10个元素各不相同,查找数组中是否存在值为key的数组元素。如果有,输出相应的下标,否则输出not found。已知数组无序排列。
    

    输入要求

    先从键盘输入10个整数。然后再输入一个待查找的数据key。
    

    输出要求

    若存在,则输出该数所在位置的下标值。若不存在则输出"not found"(输出不包含双引号)。
    

    输入样例

    6 70 -9 80 83 54 3 88 10 2
    80
    

    输出样例

    3
    

    提示

    数组的下标从0开始

    参考程序

    #include<stdio.h>
    
    void main()
    {
    	int f[10], i, x, c = 0;
    	
    	for (i = 0; i < 10; i++)
    		scanf("%d", &f[i]);
    	scanf("%d", &x);
    	for (i = 0; i < 10; i++)
    	{
    		if (x == f[i])
    		{	printf("%d\n", i);
    			break;
    		}
    		else
    			c++;
    	}
    	if (c == 10)
    		printf("not found\n");
    }

     

    更多相关内容
  • 首先,在数组查找指定值,首先想到的就是折半查找法(二分法),但在折半法中,要求数组必须是有序的,所以可以先将数组内的数据进行相关的排序工作后,再运用二分法查找。int BinarySearch(int* array,int size,int...

    首先,在数组中查找指定值,首先想到的就是折半查找法(二分法),但在折半法中,要求数组必须是有序的,所以可以先将数组内的数据进行相关的排序工作后,再运用二分法查找。

    int BinarySearch(int* array,int size,int value);//折半查找

    int BubbleSort(int* array,int* size,int is_desc);//冒泡排序

    所以,最终决定先采用冒泡排序(BubbleSort)的方法将数组列为有序的,再用折半查找(BinarySrarch),查找到指定元素。

    冒泡排序

    冒泡排序就是把小的元素往前调或者把大的元素往后 调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

    冒泡排序的思想(升序排序):每次循环找出一个待排序区间中的最大值,安放在合适的位置上,循环N次就能够把N个值都放好,最终保数组是有序的。

    int BubbleSort(int* array,int* size,int Is_Desc){

    //在函数的定义中,数组会影视转换为指针,指向数组的首元素

    //数组的长度可以用size = sizeof(arr) / size(arr[0])

    //Is_Desc是用来判定是升序排列还是降序排列

    int bound = 0;

    //[0,bound):已经排好序的区间

    //[bound,size]:待排序的区间

    for(;bound < size;++bound){

    //这个循环执行一次之后,就找出了当前待排区间的最小/大值,并放到了首位

    for(int cur = size - 1;cue > bound;--cur){

    //cur是后面的元素,cur - 1是前面的元素

    //此时就需要进行升序排序,如果发现后面的元素比前面的元素小,就交换两个元素的值

    if(Is_Desc == 0){

    //升序排序

    if(array[cur - 1] > array[cur]){

    //进行交换

    Swap(&arr[cur],&arr[cur - 1]);

    }

    }else if(Is_Desc == 1){

    //降序排序

    if(arr[cur] < arr[cur -1]){

    Swap(&array[cur],&array[cur - 1]);

    }

    }

    }

    }

    return;

    }

    折半查找

    int BinarySearch(int* array, int size, int value) {

    int left = 0;

    int right = size - 1;

    int mid = 0;

    while (left <= right) {

    mid = (right + left) / 2;

    if (array[mid] < value) {

    left = mid + 1;

    }

    else if (array[mid] > value) {

    right = mid - 1;

    }

    else {

    break;

    }

    }

    if (left <= right) {

    printf("Find it!The Num is %d!\n", mid);

    }

    else {

    printf("Can't find it!\n");

    }

    return 1;

    }

    最终程序

    #include#includevoid Swap(int* a,int* b ) {

    int tmp = *a;

    *a = *b;

    *b = tmp;

    }

    int BubbleSort(int* array, int size,int Is_Desc) {

    int bound = 0;

    for (; bound < size; ++bound) {

    for (int cur = size - 1; cur > bound;--cur) {

    if (Is_Desc == 0) {

    if (array[cur] < array[cur - 1]) {

    Swap(&array[cur],&array[cur - 1]);

    }

    }

    else if (Is_Desc == 1) {

    if (array[cur - 1] < array[cur]) {

    Swap(&array[cur], &array[cur - 1]);

    }

    }

    }

    }

    return;

    }

    int BinarySearch(int* array, int size, int value) {

    int left = 0;

    int right = size - 1;

    int mid = 0;

    while (left <= right) {

    mid = (right + left) / 2;

    if (array[mid] < value) {

    left = mid + 1;

    }

    else if (array[mid] > value) {

    right = mid - 1;

    }

    else {

    break;

    }

    }

    if (left <= right) {

    printf("Find it!The Num is %d!\n", mid);

    }

    else {

    printf("Can't find it!\n");

    }

    return 1;

    }

    int main()

    {

    int arr[] = {98,65,12,33,54,13,38,1,100,20};

    int size = sizeof(arr) / sizeof(arr[0]);

    int value = 13;

    BubbleSort(arr, size, 0);

    BinarySearch(arr,size,value);

    system("pause");

    return 0;

    }

    程序运行结果

    3537970e14d10998a3a5292a4bc917a9.png

    展开全文
  • LeetCode 数组问题 元素查找问题

    限定范围内的元素查找

    41. 缺失的第一个正数 H

    给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。Link

    • 空间复杂度为O(n)的辅助数组解法
    • 理论基础
      • 1、假设数组中的元素个数为 n,则小于1的元素以及大于 n 的元素不会影响最小正整数的判断,因此此时最小正整数肯定取 1
      • 2、[1, n] 区间范围内的正整数,其出现与否影响最小正整数的取值
    • 实现思路
      • 统计 [1, n] 区间范围内的正整数的出现情况,输出没出现的最小的正整数即可
      • 1、若部分出现,输出第一个没出现的正整数
      • 2、若全未出现,输出 1 即可
      • 3、若全部出现,输出 n + 1 即可
    • 1、2两种情况可进行合并,因为全未出现时,第一个没出现的正整数肯定为 1
    class Solution {
    public:
        int minNumberDisappeared(vector<int>& nums) {
            int n = nums.size();
            vector<int> arr(n, 0);
            for (int i = 0; i < n; i++) {
                if (0 < nums[i] && nums[i] <= n) {
                    arr[nums[i] - 1] = nums[i]; // 记录有效区间范围内的正整数
                }
            }
            for (int i = 0; i < n; i++) {
                if (arr[i] != i + 1) return i + 1;
            }
            return n + 1;
        }
    };
    
    • 空间复杂度为常数级别的原地置换方法
    • 实现思路
      • 1、将 [1, n] 区间范围内的正整数 num 交换至 num - 1位置
      • 2、将 [1, n] 区间范围外的正整数、第 i 个位置的值为 i + 1 的情况均不做处理
        • *若 [1, n] 区间范围内的正整数重复出现,可能会重复交换,陷入死循环,加条件判断:即判断其要交换的位置 i 是否满足值为 i + 1,若满足说明不用交换,直接跳过即可
      • 3、重新遍历数组,第一个不满足位置 i 的值为 i + 1的时候,i + 1就是缺失的第一个正整数,如果均满足,则结果 n + 1
    class Solution {
    public:
        int minNumberDisappeared(vector<int>& nums) {
            int n = nums.size();
            for (int i = 0; i < n; i++) {
                if (nums[i] == i + 1) continue;
                // 数字在有效区间范围内,并且其要交换的位置还未得到合适的元素值
                while (0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                    swap(nums[i], nums[nums[i] - 1]);
                }
            }
            for (int i = 0; i < n; i++) {
                if (nums[i] != i + 1) return i + 1;
            }
            return n + 1;
        }
    };
    

    287. 寻找重复数 M

    给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。Link

    • 将每个元素交换至其下标处,查找不符合对应条件的值即可
    • 1、[1, n] 之间的值 i 交换至下标 i - 1处,除了重复值以外,其他元素均能一一对应
    • 2、重新遍历数组,寻找不符合对应条件的那个值就是重复值
    class Solution {
    public:
        int findRepeatNum(vector<int>& nums) {
            int n = nums.size();
            for (int i = 0; i < n; i++) {
                if (nums[i] == i + 1) continue;
                while (nums[nums[i] - 1] != nums[i]) {
                    swap(nums[i], nums[nums[i] - 1]);
                }
            }
            for (int i = 0; i < n; i++) {
                if (nums[i] != i + 1) return nums[i];
            }
            return -1;
        }
    };
    
    • 参考环形链表问题,不修改数组
    • 1、建立下标和元素的映射关系,以 [1,3,4,2] 为例
      • [1,3,4,2]
      • [0,1,2,3]
      • 从下标 0 开始,根据下标指向的元素遍历,则有 ‘0’ - 1 - 3 - 2 - 4 - NULL
    • 2、若数组中存在重复的数字,则有
      • [1,3,4,2,2]
      • [0,1,2,3,4]
      • 从下标 0 开始,则有 ‘0’ - 1 - 3 - 2 - 4 - 2 - 4 - 2 ·····,进入死循环
    • 3、类比环形链表的处理方法进行处理
      • fast、slow 指向头节点 0
      • fast 每次走两步,即 fast = nums[nums[fast]]
      • slow 每次走一步,即 slow = nums[slow]
    • 4、fast、slow相等则说明存在重复元素,即链表有环
    • 5、fast 指向头节点,每次走一步,fast、slow再次相遇的位置即重复元素值,即入环点
    class Solution {
    public:
        int findRepeatNum(vector<int>& nums) {
       		// 同一起点,快慢指针开始
            int fast = 0, slow = 0;
            fast = nums[nums[fast]];
            slow = nums[slow];
            while (slow != fast) {
                fast = nums[nums[fast]];
                slow = nums[slow];
            }
            
            // 找到入环点,即重复元素
            fast = 0;
            while (fast != slow) {
                fast = nums[fast];
                slow = nums[slow];
            }
            return fast;
        }
    };
    

    与出现次数相关的元素查找

    136. 只出现一次的数字

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。Link

    • 位运算、异或
    • 1、两个相同的数异或结果为0
    • 2、一个数与 0 异或结果不变
    • 3、使用 0 与数组中的所有数异或,最终结果就是出现一次的数字
        int singleNumber(vector<int>& nums) {
            int x = 0;
            for (auto & num : nums) {
                x = x ^ num;
            }
            return x;
        }
    

    260. 只出现一次的数字 III

    给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。Link

    • 位运算
    • 假设两个出现一次的元素为 x、y,则数组所有数字异或的结果就等于 x ^ y,记为 z
    • 1、z 中所有为 1 的位置是 x 或 y 中所独有的 1,取 mask 为 z 中第一个 1,这个 1 为 x 或 y 所独有的
    • 2、利用数字与 mask 相与的结果分成两组,这样 x、y 可以落进不同的组中,转化为 260题的求解方式
    • & 的优先级低于 ==

    class Solution {
    public:
        vector<int> singleNumber(vector<int>& nums) {
            int z = 0;
            for (auto &num : nums) {
                z ^= num;
            }
            int mask = 1;
            // & 优先级低于 ==,此处必须对位运算的结果加括号
            while ((mask & z) == 0) {
                mask = mask << 1;
            }
            int x = 0, y = 0;
            for (auto &num : nums) {
                if ((num & mask) != 0) x ^= num;
                else y ^= num;
            }
            return {x, y};
        }
    };
    
    

    137. 只出现一次的数字 II

    给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。Link

    • 位运算
    • 三个相同的数字,统计每一个二进制位上 1 的个数,必定为 3 的整数倍,对 3 取余便是只出现一次的那个二进制位,组合结果便为只出现一次的数字
    • 1、统计每个二进制位上 1 的个数
    • 2、对 3 取余,然后赋值给结果对应的二进制位上
    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            vector<int> cnt(32, 0);
            for (int i = 0; i < nums.size(); i++) {
                int num = nums[i];
                unsigned int flag = 1;
                for (int i = 31; i >= 0; i--) {
                    if ((num & flag) != 0) {
                        cnt[i]++;
                    }
                    flag = flag << 1;
                }
            }
            int ans = 0;
            for (int i = 0; i < 32; i++) {
                ans = ans << 1;
                ans = ans | (cnt[i] % 3);
            }
            return ans;
        }
    };
    
    • 一种简化的版本:即求即算
    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int ans = 0;
            for (int i = 0; i < 32; i++) {
                int cnt = 0;
                for (int num : nums) {
                    cnt += (num >> i) & 1;
                }
                if (cnt % 3) {
                    ans |= (1 << i);
                }
            }
            return ans;
        }
    };
    
    • 数字电路、状态机

    • 1、各二进制位上 1 的个数除以 3 的余数共有三种状态:0、1、2,状态转换如图
      在这里插入图片描述

    • 2、用两个比特 b a 表示这 3 种状态,即
      在这里插入图片描述

    • 3、首先计算低位比特 a 的更新情况:a = a ^ x & ~b

    • 4、比特 a 更新结束以后的状态转换为(假定输入 x 均为 1)
      在这里插入图片描述

    • 5、将 b a 的位置对调,并调整状态位置
      在这里插入图片描述

    • 5、比特 b 的更新情况与 a 相同:b = b ^ x & ~ a

    • 6、其与二进制位的更新情况相同

    • 7、遍历结束,各二进制位的状态为 0 或 1,即 00、01,是由比特 a 记录的,因此返回 a 即可。

    图片引用自LeetCode K神的题解,Link

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int b = 0, a = 0;
            for (int x : nums) {
                a = a ^ x & ~b;
                b = b ^ x & ~a;
            }
            return a;
        }
    };
    

    展开全文
  • 设计一个查找算法,该算法将在一个给定的无序数组查找指定的元素,若找到该元素返回true,反之返回false。请分析你所设计算法的时间复杂度。 要求 编写并测试所设计的查找算法 实验报告中还需要包含对所设计算法的...

    一、任务描述

    设计一个查找算法,该算法将在一个给定的无序数组中查找指定的元素,若找到该元素返回true,反之返回false。请分析你所设计算法的时间复杂度。

    二、要求

    编写并测试所设计的查找算法
    实验报告中还需要包含对所设计算法的时间复杂度分析过程。

    三、步骤描述

    运用时间内存分配,输入数组的大小,利用随机数生成数组需要的随机数(随机数范围<=100),直接按数组顺序求复合条件的数,时间复杂度为O(n)。

    四、程序运行结果截图

    1
    2
    3

    五、源代码(C++)

    #include<iostream>
    #include<ctime>
    #include<Windows.h>
    
    using namespace std;
    
    int main()
    {
        DWORD start_time=GetTickCount();
        srand(time(NULL));
        int n;
        cout<<"Please enter the number of array size :";
        cin>>n;
        int a[n],i,x,flag=0;
        cout<<endl<<n<<" random arrays are being generated,please wait !"<<endl<<endl;
        for(i=0;i<n;i++)
        {
            a[i]=rand()%100;
        }
        cout<<n<<" random arrays generation completed !"<<endl<<endl;
        cout<<"Please put the number you want find :";
        cin>>x;
        cout<<endl;
        for(i=0;i<n;i++)
        {
            if(a[i]==x && flag==0)
            {
                cout<<"true"<<endl<<endl;
                flag=1;
            }
        }
        if(flag==0)
        {
            cout<<"false"<<endl<<endl;
        }
        DWORD end_time = GetTickCount();
        cout<<"The run time is :"<<(end_time-start_time)<<"ms!"<<endl;
        return 0;
    }
    
    
    展开全文
  • 无序数组的查询

    2021-06-29 14:35:58
    #include <stdlib.h> #include <stdio.h> int main() { int nums[10] = {0, 10, 6, 296, 177, 23, 0, 100, 34, 999};//数组 ...//a代表数组下标b代表目标的下标c代表输入的数 ...a++) //在十个数组里循环查.
  • 无序数组查找比K大确不存在数组中的最小正整数。 说明 数组arr=[]string{5,2,4,8},k=1,则结果为3。 代码 func TestFindMissing(t *testing.T) { for i, tc := range []struct { target int arr []int k int...
  • 无序数组去重算法

    2022-02-18 14:44:15
    无序数组去重算法 无序数组去重算法的复杂度是O(n2)。 代码如下,首先进行外层循环,复杂度O(n),然后查找这个元素之前的元素中有没有重复的,复杂度O(n),如果有就删除,复杂度O(1),没有就下一个元素,复杂度O(1)。...
  • 数组元素查找 无序查找 线性查找
  • //无序数组查找 public Boolean dicordNunberCheck(int[] numbers, int value) { //23,77,66,44,88 //int value= 23; Boolean isOk= false; //int[] numbers= {23, 77, 66, 44, 88}; for(int i=0; i;...
  • 数组 数组的定义 数组是相同类型数据的有序集合,数组描述的是相同类型的若干个数据,按照一定的先后次序排列组合而成。其中,每一个数据称作一个元素,每个元素可以通过一个索引(下标)来访问它们。数组的三个基本...
  • 无序数组 增 添加数据 ,首先先将数组转移到另一个空间遍历一遍时间复杂度为O(n),再添加 总计时间复杂度为O(n) 删 先查找数据复杂度为O(n)然后删除 添加的数后面索引减一 时间复杂度O(n) 总计时间复杂度为O(n) ...
  • 无序数组找中位数

    千次阅读 2021-04-04 09:27:11
    1.无序数组找中位数 思路一 把无序数组排好序,取出中间的元素 时间复杂度 采用普通的比较排序法 O(N*logN) 如果采用非比较的计数排序等方法, 时间复杂度 O(N), 空间复杂度也是O(N). 思路二 (1)将前(n+1)/2个...
  • 今天小编就为大家分享一篇关于Java查找不重复无序数组中是否存在两个数字的和为某个值,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 利用排序进行查找中位数 基本思路:对数组进行排序,直接访问数组中位数 double MIDnum(vector<int>& array) { if(array.empty()) return -1; int midIndex = (array.size() - 1) / 2; sort(array....
  • 1.二分查找输入查找值,返回查找值的数组下标(查找数组arr,数组的开头start,数组的结尾end,查找的值key) 先判断输入的start(开头)是否比end(结尾)大,如果比end(结尾)大返回-1; 2.在以上的大范围之下...
  • 折半查找又称为二分查找或对分查找。 (1)基本的二分查找 使用条件: 1. 线性表中的记录必须按关键码有序。 2. 必须采用顺序存储结构。 基本思想: 在有序表中,取中间记录作为比较对象, 若给定值与中间...
  • 无序数组元素查找

    2021-06-02 23:35:19
    public class TestHalfSrh{ public static void...//要查找的元素 int length1 = a.length/2; int length2 = a.length; String str = null; while(length2/2 > 0){ for(int i = length1; i 输出结果: null
  • 由于只要求找出第k大的数,没必要将数组中所有值都排序。 典型解法:快速排序分组。 在数组中找到第k大的元素 取基准元素,将元素分为两个集合,一个集合元素比基准小,另一个比基准大 ,三种情况。 1.比基准大的...
  • 二分查找方法很简单,理解了局部最小的定义,二分查找很快搞定这个题,今后遇到查找的话,尽量敏感地想到二分查找
  • 在发文时会有一种情况,此排序码...1、获得此文件种类排序码最大值,从0到排序码最大值形成一个数组newArr。 2、获取此文件种类所有排序码,并将它们形成数组oldArr。 3、取两个数组中不同的元素并输出,输出的元素就为
  • 问题:给定一个无序数组,找出该无序数组的第k大元素。 思路:1.先排序,那么第k个元素自然就是第k大的元素了。 2.使用最小堆,先利用前k个元素建立最小堆,再往后比较,如果有比堆顶元素大的,则调整最小堆,最后...
  • 求一个无序数组中两个数的下标,他们加起来为给定值 首先这个题是无序的,所以不能用两个指针遍历得到,如果排序之后再遍历,那样复杂度是O(nlogn)而且返回的是原来的下标。所以不能这么做。 只能利用哈希表来用...
  • 无序数组中 两个相同的数 解题思路: 这道题我们可以采用二分法来找到数组中重复的元素下标,输出即可 此方法仅限于寻找数组中只有两个相同的数,局限性比较大,可作为参考 代码如下: import java.util.Arrays; ...
  •   中位数(又称中值,英语:Median),统计学中的专有名词,代表一个样本、种群或概率...  面试时,大家是不是经常被问到,怎么求一个无序数组(长度为n)的中位数?   面试官:知道什么是中位数吗?   ...
  • System.out.println("-------查找数组第K大的值结果------"); System.out.println(result); } private static int findNumK(int[] arr, int k) { //1. 用前K个元素构建小顶堆 buildHeap(arr, k); //2. ...
  • 我们选择数组区间 A[0…n-1]的最后一个元素 A[n-1]作为 pivot,对数组 A[0…n-1]原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1=K,那 A[p]就是要求解的元素;如果 K>p+1, 说明第 K ...
  • 1、概念 以下摘自百度百科:对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。 由概念可得,对于一个有小到大排序好...
  • 寻找无序数组中的第K大元素

    千次阅读 2019-01-23 17:31:33
    方法一:排序法,先把这个无序数组进行排序,假设按照从小到大排,则第k个元素就是数组中的第k大元素。 排序的时间复杂度最快为o(nlogn) 下面用快速排序实现: #include&lt;iostream&gt; template&lt;...
  • 逆天!对无序数组使用二分查找

    千次阅读 多人点赞 2018-07-17 22:58:46
     所谓的无序数组并不是乱序,我们会遇见很多情况是旋转数组,比如一个递增数组最开始的几个元素挪到数组的最后位置。也可以理解成是两个有序数组的组合。 面试题:打印出旋转数组的最小数字  题目:把一个数组...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 71,981
精华内容 28,792
关键字:

无序数组的查找